Linked Lists

Implementation in Python#

Basic LinkedList#

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)
# Empty linked list
if self.head is None:
self.head = new_node
return
# Append reference to last node
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
# Insert at start
def prepend(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def print_linked_list(self):
curr_node = head
while(curr_node):
print(curr_node.data)
curr_node = curr_node.next

Insert After a Node#

# Insert new node after given 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

Delete a Node#

def delete_node(self, value):
curr_node = self.head
# if deleting the head
if curr_node and curr_node.data == value:
self.head = curr_node.next
curr_node = None
return
# deleting other nodes
prev = None
while(curr_node and curr_node.data != value):
prev = curr_node
curr_node = curr_node.next
# node not found
if curr_node is None:
return
# node found
else:
prev.next = curr_node.next
curr_node = None
def delete_at_position(self, pos):
if(self.head):
curr_node = self.head
# delete head
if pos == 0:
self.head = curr_node.next
curr_node = None
return
# count steps and delete node
prev = None
count = 0
while curr_node and count != pos:
prev = curr_node
curr_node = curr_node.next
count += 1
# we reached end of linked list, but couldn't reach the pos required
if curr_node is None:
return
# node found, delete it
prev = curr_node.next
curr_node = None

Length of Linked List#

def length(self):
count = 0
curr_node = self.head
while curr_node:
count += 1
curr_node = curr_node.next
return count
def length_recursive(self, node):
if(node is None):
return 0
return 1 + self.length_recursive(node.next)

Swap Two Nodes#

def swap_nodes(self, key1, key2):
if key1 == key2:
return
# get the first node
node_1 = None
curr_1 = self.head
while curr_1 and curr_1.data != key1:
node_1 = curr_1
curr_1 = curr_1.next
# get 2nd node
node_2 = None
curr_2 = self.head
while curr_2 and curr_2.data != key2:
node_2 = curr_2
curr_2 = curr_2.next
if not curr_1 or not curr_2:
return
if prev_1:
prev_1.next = curr_2
else:
self.head = curr_2
if prev_2:
prev_2.next = curr_1
else:
self.head = curr_1
curr_1.next, curr_2.next = curr_2.next, curr_1.next

Reverse Linked List#

Iterative Version#

def reverse(self):
prev = None
curr = self.head
while curr:
next = curr.next # store next link
curr.next = prev
prev = curr
curr = next
self.head = prev

Recursive Version#

def reverse_recursive(self):
# internal method
def _reverse_recursive(curr, prev):
if not curr:
return prev
next = curr.next
curr.next = prev
prev = curr
curr = next
return _reverse_recursive(curr, prev)
self.head = _reverse_recursive(curr = self.head, prev = None)

LinkedLists vs Arrays#

Advantages of a LinkedList over Arrays#

  • Dynamic size
    • We do not need to decide on a fixed size when we initialise (unlike arrays, even ArrayList in Java works with a fixed initial size and thereafter doubles whenever required)
    • You can add or remove items from the beginning of the list in constant time.
    • As compared to arrays, if you need to insert/remove some data, usually we need to shift the rest of the elements
  • Ease of insertion and deletion with O(1) time vs O(n) for inserting and deleting at the start of array
  • LinkedList is a recursive structure (though iterative solutions can be also used effectively)

Drawbacks of LinkedLists#

  • Random access is not allowed and access is only done sequentially. LL does not provide constant time access to a particular index. Time complexity: O(k) to find kth element.
  • Hence, binary search is not applicable.
  • Extra memory space for each element for pointer
  • Arrays have better cache locality which makes a big difference in performance
  • Arrays have contiguous memory whereas linked lists do not