A Linked List is a data structure that stores a list of items where each element, which is called a
Node, is an object that stores a value and also a pointer to the next Node in the list.
Benefits of linked list
- No fixed size
- Adding an element to the front takes
- Removing an element to the front takes
Downsides of a linked list
- It will take
O(n)runtime to access a value by the index since we must start from the
headand traverse until we find the desired
- Searching for an element will take
O(n)runtime as we would have to start from the head and traverse the entire list.
|value||Value stored by this node|
|next||Pointer to next node in the list|
Reversing a linked list
Input: 1 => 2 => 3 => 4 => NULL
4 => 3 => 2 => 1 => NULL
Reverse the pointers on each
node so that each
node points to the next
node. To do this you’ll need 3 temporary pointers
prev, current, next. We will traverse the list and set the
prev each step. We require
3 temporary pointers because otherwise, we won’t be able to track the next Node in the list since we are redirecting the next pointers of current.
Arrays require a block of contiguous memory where as linked list do not. This results in O(1) lookups for arrays but O(n) for linked lists.
|Insertion/Deletion at the beginning of the array or linked list given a value||O(n)||O(1)|
- Array Insertion for an array is O(n) because all elements needed to be shifted to the right.
- Linked list Insertion at the
HEADis O(1) because all you have to do is update the pointer.
Doubly linked list
- Every node as a pointer to the
nextnode and a pointer to the
Linked list cycles
Linked List Skeleton class
class Node: def __init__(self, item, next=None): self.item = item self.next = next class LinkedList: def __init__(self): pass def __str__(self): pass def insertFront(self, item): pass def insertLast(self, item): pass def removeBeginning(self): pass
Full linked list implementation
class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def append(self, data): new_node = Node(data) if self.head is None: self.head = new_node return # start from the head pointer last_node = self.head # iterate through each node starting from head until we hit the # last_node which is none while last_node.next: last_node = last_node.next # once there insert new_node last_node.next = new_node def prepend(self, data): new_node = Node(data) new_node.next = self.head self.head = new_node def insert_after_node(self, prev_node, data): if not prev_node: print("Previous node does not exist.") return new_node = Node(data) new_node.next = prev_node.next prev_node.next = new_node def print_list(self): # similar to append, we start from head cur_node = self.head while cur_node: print(cur_node.data) cur_node = cur_node.next def delete_node(self, key): cur_node = self.head if cur_node and cur_node.data == key: self.head = cur_node.next cur_node = None return prev = None while cur_node and cur_node.data != key: prev = cur_node cur_node = cur_node.next if cur_node is None: return prev.next = cur_node.next cur_node = None if __name__ == "__main__": llist = LinkedList() llist.append("a") llist.append("b") llist.append("c") llist.prepend("d") llist.insert_after_node(llist.head.next, "E") llist.print_list() print("Deleting node a") llist.delete_node("a") llist.print_list()