Linked List Background
For more background on the different types of data structures in Python, check out the following articles:
Table of Contents
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.
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.
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.
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.
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
Last updated