Linked List Background

For more background on the different types of data structures in Python, check out the following articles:

• Introduction

• List

• Stack

• Queue

Table of Contents

• Linked List: Introduction

• Uses of Linked Lists

• Implementing Linked Lists

• Practice Linked Lists

• Conclusion

Linked List: Introduction

A Linked List is a linear data structure. They are a sequence of data, connected together by links or pointers.

Linked Lists are a chain of nodes, connected together by links. Every node (fundamental block of a linked list) contains the following fields:

• Data -> The item to be stored in the node.

• Next -> The link or reference to the next node.

In a linked list, the first node is called the head and the last node is determined by the condition that the next points to a null value.

Null, Linked List

Uses of Linked Lists

• Due to their dynamic size allocation and ease of insertion/deletion, linked lists are applied in a lot of use cases.

• They’re used to implement a lot of complex data structures like the adjacency list in graphs.

• They are used for lifecycle management in operating systems.

• A playlist in a music application is implemented using a doubly linked list.

• Blockchain, a complex data structure that is used for cryptocurrencies and ledgers use a linked list at their core.

Implementing Linked Lists

There are two main types of Linked Lists:

• Singly Linked Lists

• Doubly Linked Lists

Singly Linked Lists

In the following example, we’ll implement a singly linked list from scratch in Python. This contains the following methods:

• ll.search(head, data) -> Search the given element in the Linked List.

• ll.print_list() -> Print the linked list.

• ll.size() -> Return the length of the linked list.

• ll.insert(ele) -> Insert the given node into the linked list.

• ll.delete(data) -> Delete the given element from the linked list.

class Node(object):
	def __init__(self, data):
		self.data = data
		self.next = None

# Class to create a Linked List
class LinkedList(object):
	def __init__(self, head=None):
		self.head = head

	# Search an element and print its index
	def search(self, head, data, index):
		if head.data == data:
			print (index)
		else:
			# Make recursive calls
			if head.next:
				return self.search(head.next, data, index+1)
			else:
				raise ValueError("Node not in linked list")

	# Print the linked list
	def print_list(self):
		if self.head == None:
			raise ValueError("List is empty")

		current = self.head 
		while(current):
			print (current.data, end="  ")
			current = current.next
		print ('\n')

	# Find length of Linked List
	def size(self):
		if self.head == None:
			return 0

		size = 0
		current = self.head
		while(current):
			size += 1
			current = current.next

		return size

	# Insert a node in a linked list
	def insert(self, data):
		node = Node(data)
		if not self.head:
			self.head = node
		else:
			node.next = self.head
			self.head = node

	# Delete a node in a linked list
	def delete(self, data):
		if not self.head:
			return
		
		temp = self.head
		
		# Check if head node is to be deleted
		if head.data == data:
			head = temp.next
			print ("Deleted node is " + str(head.data))
			return

		while(temp.next):
			if (temp.next.data == data):
				print ("Node deleted is " + str(temp.next.data))
				temp.next = temp.next.next
				return
			temp = temp.next
		print ("Node not found")
		return

Doubly Linked Lists

A doubly linked list is similar to a singly linked list. It differs in that it also contains a link to the previous node.

We implement the following methods for the Doubly Linked List data structure:

• dll.addNodeLast(x) -> Adds a node at the right end of the linked list.

• dll.insertNode(pos, x) -> Adds a node at the position specified.

• dll.removeNode(x) -> Removes the specified node.

• dll.showReverse() -> Prints the linked list in reverse.

• dll.show() -> Prints the linked list.

class Node:
    def __init__(self, val):
        self.value = val
        self.next = None
        self.prev = None
    
class DoublyList:
    def __init__(self, val):
        self.head = Node(val)
        self.tail = self.head

    def addNodeLast(self, val):
        current = self.head
        while current.next != None:
            current = current.next
        newNode = Node(val)
        current.next = newNode
        newNode.prev = current
        self.tail = newNode

    def insertNode(self, val, newVal):
        if self.tail.value == val:
            self.addNodeLast(newVal)
        elif self.head.value == val:
            newNode = Node(newVal)
            newNode.next = self.head.next
            newNode.prev = self.head
            newNode.next.prev = newNode
            self.head.next = newNode
        else:
            current = self.head.next
            while current.value != val:
                current = current.next
            newNode = Node(newVal)
            newNode.next = current.next
            newNode.next.prev = newNode 
            newNode.prev = current
            current.next = newNode

    def removeNode(self, val):
        if self.head.value == val:
            self.head = self.head.next
            self.head.prev = None
        elif self.tail.value == val:
            self.tail = self.tail.prev
            self.tail.next = None
        else:
            current = self.head.next
            while current.value != val:
                current = current.next
            current.prev.next = current.next
            current.next.prev = current.prev

    def showReverse(self):
        current = self.tail
        while current != None:
            print(current.value)
            current = current.prev

    def show(self):
        current = self.head
        while current != None:
            print(current.value)
            current = current.next

Practice Linked Lists

First, try implementing the Linked Lists as shown above, and then try running them. Once you’ve mastered the implementation, try the given problem-sets to master linked lists.

• Merge Two Sorted Lists - LeetCode
• Remove nth Node from the End of the List - LeetCode
• Rotate List - LeetCode
• Palindrome Linked List - LeetCode
• Construct a Doubly Linked List from 2D Matrix - GeeksforGeeks
• Reverse a Doubly Linked List - GeeksforGeeks