Pythonインタビュー質問ガイド:リンクリストのコーディング方法

私はリンクリストのコアコンセプトを常に理解していましたが、それを実践することはありませんでした。

リンクリストの概念がどのようにコードに変換されるのかわからないことに気付いたのは、数年前の最初のAmazonインタビューまででした。

そしてそれが私がこのガイドを書いている理由です!

私の目標は、ソフトウェアエンジニアとしての仕事を手伝うことです

リンクリストのインタビューの質問をたくさん取り上げたいのですが、この記事はそのプロセスの最初のステップです。では、に飛び込みましょう。

リンクリストとは何ですか?

リンクリストは、「ノード」と呼ばれる多くのミニデータ構造で構成されるデータ構造です。ノードは互いにリンクしてリストを形成します。

各ノードには2つの属性が含まれています

  1. その価値。これは、整数、文字、文字列、オブジェクトなど、何でもかまいません。
  2. シーケンス内の次のノードへのポインタ。

いくつかの定義

「ヘッドノード」:ヘッドノードは、リンクリストの最初のノードにすぎません。上記の例からわかるように、「5」を含むノードが最初のノードであり、したがってヘッドです。

「テールノード」:テールノードは、シーケンスの最後のノードです。これは最後のノードであるため、シーケンスに次のノードがないため、nullを指します。上記の例では、「3」を含むノードがテールノードになります。

単一リンクと二重リンク

リンクリストに関しては、主に2つの種類があります。

「単独で」リンクされているものと「二重に」リンクされているもの。

単一リンクとは、各ノードが最大で1つの他のノード、つまりその前のノードのみを指すことを意味します。これは上記の例に示されています。

二重リンクとは、各ノードが他の2つのノード、つまりその前のノードとその後ろのノードを指すことができることを意味します以下の例からわかるように、ヘッドノード(5)の前にノードがないため、そのポインターの1つがnullを指しています。

さて、私はそれをすべて理解しています。しかし、コードはどのように機能しますか?

リンクリストのコーディングには、4行の問題または400行の問題があります。それはあなたがそれにどのようにアプローチしたいかによります。

最も単純なレベルでは、前述したように、リンクリストは接続されたノードの集まりにすぎません

したがって、この構造を作成するために実際に必要なのはノードオブジェクトだけです。

class linkedListNode: def __init__(self, value, nextNode=None): self.value = value self.nextNode = nextNode

ここでは、valueとnextNode属性を持つクラスを作成しただけであることがわかります。

ノードを作成するには、値を渡すだけです。

node1 = linkedListNode("3") # "3"node2 = linkedListNode("7") # "7"node3 = linkedListNode("10") # "10"

ここでは、3つの個別のノードを作成しました。

次のステップは、単にそれらを接続することです。

node1.nextNode = node2 node2.nextNode = node3 

上記の最初の行は、node1がnode2を指すようにします。

「3」→「7」

上記の2行目は、node2がnode3を指すようにします。

「7」→「10」

まとめると、次のようなリンクリストが残ります。

「3」→「7」→「10」→Null

注:node3にnextNodeが割り当てられておらず、デフォルトのnextNodeがNullであるため、「10」はnullを指します。

前に述べたように、これを行うにはさまざまな方法があります。これは最も簡単です。

LinkedListクラス全体を作成しようとしている場合、このビデオではその方法について詳しく説明します。

リンクリストのトラバース

プログラミングのインタビューを行っていて、リンクリストの質問をされた場合、すべてのノードが提供されるわけではありません。

取得するのはヘッドノードだけです。

そのヘッドノードから、リストの残りを取得する必要があります。

First let’s understand how to get the value and nextNode from a node in Python.

Let’s say we have a node simply named ‘node’.

Getting the value of the node:

node.value

Getting the nextNode of the node:

node.nextNode

Traversal

This first thing we want to do is create a variable called “currentNode” that keeps track of the node we’re at. We want to assign this to our head node at first.

currentNode = head

Now all we have to do is simply check whether or not our current node is Null. If it’s not, we make our ‘currentNode’ equal to the ‘nextNode’ of the ‘currentNode’.

currentNode = node1while currentNode is not None: currentNode = currentNode.nextNode

Let’s say we have the following Linked List: “3”→”7"→”10".

Our head and first ‘currentNode’ is “3”.

When we do

currentNode = currentNode.nextNode

We are reassigning ‘currentNode’ to our current node’s neighbor, which in this case is “7”.

This continues until the currentNode is pointed to None, in which case the loop stops.

And that is the basic way to traverse through a Linked List in Python.

Link to the code on Github.

Inserting elements

When you insert an element into a linked list, you insert it into the back unless specified otherwise.

Let’s use the following example:

“3”→”7"→”10"→Null

Let’s say we want to insert a “4”.

We would simply find the tail node, in this case “10”, and set its nextNode to our “4” node.

“3”→”7"→”10"→“4”→Null

node4 = linkedListNode("4")node3.nextNode = node4

Now let’s say we were in an interview, and all we had was the head node.

We simply traverse through the LinkedList to find the tail. Once we have the tail, we simply set its nextNode to our new node that we create.

def insertNode(head, valuetoInsert): currentNode = head while currentNode is not None: if currentNode.nextNode is None: currentNode.nextNode = linkedListNode(valuetoInsert) return head currentNode = currentNode.nextNode

Deleting elements

Deleting can get a bit tricky.

Let’s take the same example.

“3”→”7"→”10"→Null

If we wanted to delete the “7”, all we need to do is point the “3” to the “10” so that the “7” is never referenced.

“3”→”10"→Null

To do this, we would have to traverse the list while not only keeping track of the currentNode, but also keeping track of the previousNode.

We would also have to account for the head node being the node we want to delete.

In the code below, we simply delete the first instance of the value we want to delete.

Note that there are many ways to accomplish this, and the solution below might not be the cleanest code you’ll see in your life. However, in the heat of an interview, the interviewer probably won’t expect textbook perfect code.

def deleteNode(head, valueToDelete): currentNode = head previousNode = None while currentNode is not None: if currentNode.value == valueToDelete: if previousNode is None: newHead = currentNode.nextNode currentNode.nextNode = None return newHead # Deleted the head previousNode.nextNode = currentNode.nextNode return head previousNode = currentNode currentNode = currentNode.nextNode return head # Value to delete was not found.

In the code above, once we find the node we want to delete, we set the previous node’s “nextNode” to the deleted node’s “nextNode” to completely cut it out of the list.

Big O Time Complexity Analysis

**NOTE** These are the time complexities for the node structure above, which is most likely to appear on an interview. In practical cases, you can store attributes in a LinkedList class to lower these complexities.

‘n’ = the amount of elements inside the Linked List.

Inserting to the back of the Linked List— We go through all n elements to find the tail and insert our new node. O(n)

Inserting to the front of the Linked List — We simply create the new node and set its nextNode to the head. No need to traverse the list. O(1)

Traversing — We go through all n elements once. O(n)

Deleting — Worst case scenario, the node we’re deleting is the last node, causing us to traverse through the entire list. O(n)

You can now tackle Linked List interview questions!

You now have the fundamental knowledge you need to start tackling Linked List interview questions!

They can start off easy, and get tough really quick.

In the next article, I’m going to go over a couple of common questions and techniques you can use to solve them.

If you’re a student looking to land your dream internship or full-time job within the next 2 years, start practicing now!

I’ve started a community (www.theforge.ca) where we connect students with mentors and industry experts that help them navigate their way to their dream job.

Thanks for reading, and good luck!