Linked Lists#

I’ll be documenting implementations and operations using a linked list here.

Resources#

Here are some resources I’ve found useful when learning about linked lists:

  1. freeCodeCamp.org’s Video

Definition of a Node#

Creating a Linked List#

Printing Each Item of a Linked List#

Summing a Linked List#

Finding a Value in a Linked List#

Get Node value at Index#

Reverse Linked List#

Zipping Two Linked Lists#

Linked List Design#

This is an implementation of a Linked List to satisfy the Leetcode Linked List card.

Tip

This has a few adjustments I made because of how the tests are structured on LeetCode, but I wouldn’t do this exactly this way. For instance node = MyLinkedList() is meaningless since it references a node without a value. I think this was done only to allow deleting the head node of a single-value linked list that would now become an empty linked list.

  1class MyLinkedList:
  2    def __init__(self, val=None):
  3        self.val = val
  4        self.next = None
  5
  6    def get(self, index: int) -> int:
  7        current = self
  8        counter = 0
  9        while current is not None:
 10            if counter == index and current.val != None:
 11                return current.val
 12            current = current.next
 13            counter += 1
 14        return -1
 15
 16    def addAtHead(self, val: int) -> None:
 17        if self.val is None:
 18            self.val = val
 19        else:
 20            old_val = self.val
 21            self.val = val
 22            old_next = self.next
 23            self.next = MyLinkedList(old_val)
 24            self.next.next = old_next
 25
 26    def addAtTail(self, val: int) -> None:
 27        next_value = self.next
 28        prev = self
 29        while next_value is not None:
 30            prev = next_value
 31            next_value = next_value.next
 32        if prev.val is None:
 33            prev.val = val
 34        else:
 35            prev.next = MyLinkedList(val)
 36
 37    def addAtIndex(self, index: int, val: int) -> None:
 38        current = self
 39        counter = 0
 40        prev = current
 41        while current is not None:
 42            prev = current
 43            if counter == index:
 44                old_val = current.val
 45                current.val = val
 46                old_next = current.next
 47                current.next = MyLinkedList(old_val)
 48                current.next.next = old_next
 49                return
 50            counter += 1
 51            current = current.next
 52        prev.next = MyLinkedList(val)
 53
 54    def deleteAtIndex(self, index: int) -> None:
 55        current = self
 56        counter = 0
 57        prev = None
 58        print(index)
 59        while current is not None:
 60            if counter == index:
 61                old_next = current.next
 62                if old_next is not None:
 63                    current.val = old_next.val
 64                    current.next = old_next.next
 65                elif prev is not None:
 66                    prev.next = None
 67                else:
 68                    self.val = None
 69            counter += 1
 70            prev = current
 71            current = current.next
 72
 73    def __str__(self):
 74        as_list = []
 75        current = self
 76        while current is not None:
 77            as_list.append(current.val)
 78            current = current.next
 79        return f"LinkedList: {as_list}".replace("[", "<").replace("]", ">")
 80
 81
 82def test_two():
 83    methods = [
 84        "MyLinkedList",
 85        "addAtHead",
 86        "addAtHead",
 87        "addAtHead",
 88        "addAtIndex",
 89        "deleteAtIndex",
 90        "addAtHead",
 91        "addAtTail",
 92        "get",
 93        "addAtHead",
 94        "addAtIndex",
 95        "addAtHead",
 96    ]
 97    vals = [[], [7], [2], [1], [3, 0], [2], [6], [4], [4], [4], [5, 0], [6]]
 98    test(methods, vals)
 99
100
101def test_one():
102    m = [
103        "MyLinkedList",
104        "addAtHead",
105        "addAtTail",
106        "addAtIndex",
107        "get",
108        "deleteAtIndex",
109        "get",
110    ]
111    v = [[], [1], [3], [1, 2], [1], [1], [1]]
112    test(m, v)
113
114
115def test_three():
116    m = ["MyLinkedList", "addAtTail", "get"]
117    v = [[], [1], [0]]
118    test(m, v)
119
120
121def test_four():
122    m = [
123        "MyLinkedList",
124        "addAtHead",
125        "addAtTail",
126        "addAtIndex",
127        "get",
128        "deleteAtIndex",
129        "get",
130        "get",
131        "deleteAtIndex",
132        "deleteAtIndex",
133        "get",
134        "deleteAtIndex",
135        "get",
136    ]
137    v = [[], [1], [3], [1, 2], [1], [1], [1], [3], [3], [0], [0], [0], [0]]
138    test(m, v)
139
140
141def test(methods, vals):
142    print("************************NEW TEST************************")
143    a = MyLinkedList()
144    returns = []
145    for method, val in zip(methods[1:], vals[1:]):
146        print(a)
147        func = getattr(a, method)
148        result = func(*val)
149        returns.append(result)
150        print(f"a.{method}({val})=".replace("[", "").replace("]", ""), result)
151        print("*" * 10)
152    print(a)
153    print(returns)
154    print("*" * 56)
155
156
157if __name__ == "__main__":
158    # some tests for this
159    # test_one()
160    # test_two()
161    # test_three()
162    test_four()