DS&A - 2. Data Structures - Lesson 1. Types of Linked Lists

[minimanimoh]

Singly Linked Lists

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, value):
        if self.head is None:
            self.head = Node(value)
            return

        # Move to the tail (the last node)
        node = self.head
        while node.next:
            node = node.next

        node.next = Node(value)
        return

    def to_list(self):
            out_list = []

            node = self.head
            while node:
                out_list.append(node.value)
                node = node.next

            return out_list

[minimanimoh]

1. while node.next: = when it comes to node?
2. indent of node.next = Node(value) => why wasn't it indented?
3. return (___) meaning?
4. whie node meaning (in def to_list) => the current node is self.head.. right?

[minimanimoh]

Doubly Linked Lists This type of list has connections backwards and forwards through the list.

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, value):
        if self.head is None:
            self.head = DoubleNode(value)
            self.tail = self.head
            return

        self.tail.next = DoubleNode(value)
        self.tail.next.previous = self.tail
        self.tail = self.tail.next
        return

[minimanimoh]

Circular Linked Lists Circular linked lists occur when the chain of nodes links back to itself somewhere. For example NodeA -> NodeB -> NodeC -> NodeD -> NodeB is a circular list because NodeD points back to NodeB creating a loop NodeB -> NodeC -> NodeD -> NodeB. A circular linked list is typically considered pathological because when you try to iterate through it, you'll never find the end. We usually want to detect if there is a loop in our linked lists to avoid these problems. You'll get a chance to implement a solution for detecting loops later in the lesson.