Mindig megértettem a kapcsolt listák alapfogalmát, de soha nem alkalmaztam a gyakorlatban.
Csak a legelső, évekkel ezelőtti Amazon-interjúm során jöttem rá, hogy fogalmam sincs, hogyan lehet a Linked Lists fogalmát kóddá alakítani.
És ezért írom ezt az útmutatót!
A célom az, hogy segítsen Önnek munkát, mint egy Software Engineer.
Sok kapcsolt listával készült interjúk kérdését szeretném bemutatni, és ez a cikk az első lépés ebben a folyamatban. Merüljünk hát be.
Mi az a linkelt lista?
A összekapcsolt lista egy adatstruktúra, amely sok „Node” nevű mini-adatstruktúrából áll. A Csomópontok összekapcsolódva egy listát alkotnak.
Minden csomópont 2 attribútumot tartalmaz
- Értéke. Ez bármi lehet: egész számok, karakterek, karakterláncok, objektumok stb.
- Mutató a sorozat következő csomópontjára.
Néhány meghatározás
A 'Head Node': A fej csomópont egyszerűen az első csomópont a csatolt listában. Amint a fenti példából láthatjuk, az „5” -et tartalmazó csomópont az első csomópont, tehát a fej.
A „ farokcsomópont ”: A farokcsomópont a sorozat utolsó csomópontja. Mivel ez az utolsó csomópont, a nullára mutat, mert a sorozatban nincs következő csomópont. A fenti példában a „3” -ot tartalmazó csomópont a farokcsomópont lesz.
Egyedül összekapcsolva vs kétszeresen összekapcsolva
Ami a kapcsolt listákat illeti, két fő típus létezik.
Azok, amelyek „egymással” és „kettősen” kapcsolódnak.
Az egyesével összekapcsolt azt jelenti, hogy minden csomópont legfeljebb 1 másik csomópontra mutat, az előtte lévő csomópontra. Ezt mutatja be a fenti példa.
A kettős összekapcsolás azt jelenti, hogy minden csomópont 2 másik csomópontra mutathat, az előtte lévő és a mögötte lévő csomópontra. Amint az alábbi példából láthatjuk, mivel a fejcsomópont előtt nincs csomópont (ami 5), az egyik mutatója nullára mutat.
Oké, mindezt értem. De hogyan működik a kód?
A összekapcsolt listák kódolása lehet 4 soros vagy 400 soros probléma. Attól függ, hogyan akarsz hozzáállni.
A legegyszerűbb szinten, amint azt már megbeszéltük, a kapcsolt lista csak egy csomó összekapcsolt csomópont.
Így a struktúra létrehozásához csak egy csomópont objektumra van szükségünk.
class linkedListNode: def __init__(self, value, nextNode=None): self.value = value self.nextNode = nextNodeItt láthatjuk, hogy egyszerűen létrehoztunk egy osztályt, amelynek van értéke és nextNode attribútuma.
Csomópont létrehozásához egyszerűen átadunk egy értéket.
node1 = linkedListNode("3") # "3"node2 = linkedListNode("7") # "7"node3 = linkedListNode("10") # "10"Itt 3 külön csomópontot hoztunk létre.
A következő lépés egyszerűen összekapcsolja őket.
node1.nextNode = node2 node2.nextNode = node3 A fenti első sor az 1. csomópontra mutat a 2. csomópontra:
„3” → „7”
A fenti második sor a 2. csomópontra mutat a 3. csomópontra:
„7” → „10”
Összességében maradt egy összekapcsolt lista, amely így néz ki:
„3” → „7” → „10” → Null
Megjegyzés: A „10” nullára mutat, mert a node3-hoz nem volt hozzárendelve nextNode, az alapértelmezett nextNode pedig Null.
Mint korábban említettem, ennek sokféle módja van. Ez csak a legegyszerűbb.
Ha egy teljes LinkedList osztályt próbál készíteni, akkor ez a videó elmélyülten ismerteti ennek módját.
Csatolt lista áthaladása
Ha programozási interjút készít, és feltesz egy Linked List kérdést, akkor nem kapja meg az összes csomópontot.
Csak a fejcsomópontot kapja.
Ebből a fejcsomópontból meg kell szereznie a lista többi részét.
Először értsük meg, hogyan lehet lekérni az értéket és a nextNode-ot egy Python csomópontból.
Tegyük fel, hogy van egy csomópontunk, egyszerűen „csomópont” néven.
A csomópont értékének lekérése:
node.valueA csomópont következő csomópontjának megszerzése:
node.nextNodeTraversal
Ez az első dolog, amit meg akarunk tenni, hogy létrehozzunk egy „currentNode” nevű változót, amely nyomon követi azt a csomópontot, ahol vagyunk. Ezt először a fejcsomópontunkhoz akarjuk rendelni.
currentNode = headMost csak annyit kell tennünk, hogy egyszerűen ellenőrizzük, hogy a jelenlegi csomópontunk Null-e vagy sem. Ha nem, akkor a 'currentNode' értéket megegyezzük a 'currentNode' 'nextNode-jával.
currentNode = node1while currentNode is not None: currentNode = currentNode.nextNodeTegyük fel, hogy a következő összekapcsolt listánk van: „3” → „7” → „10”.
A fejünk és az első 'currentNode' értéke „3”.
Amikor megtesszük
currentNode = currentNode.nextNodeA „currentNode” elemet hozzárendeljük jelenlegi csomópontunk szomszédjához, amely ebben az esetben „7”.
Ez addig folytatódik, amíg a currentNode a None-ra nem mutat, ebben az esetben a hurok leáll.
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 = node4Now 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.nextNodeDeleting 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!