Linked Lists

Implementation in Python#

Basic LinkedList#

class Node:
def __init__(self, data): = data = 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
# Append reference to last node
last_node = self.head
last_node = = new_node
# Insert at start
def prepend(self, data):
new_node = Node(data) = self.head
self.head = new_node
def print_linked_list(self):
curr_node = head
curr_node =

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")
new_node = Node(data) = = new_node

Delete a Node#

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

Length of Linked List#

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

Swap Two Nodes#

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

Reverse Linked List#

Iterative Version#

def reverse(self):
prev = None
curr = self.head
while curr:
next = # store next link = 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 = = 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