Linked Lists
- Here are different operations that are commonly performed on Singly, Doubly, and Circular Linked Lists
- Code and Step-by-Step diagrams/Notes are provided
Singly Linked Lists:
A new Class “Node” is required to create the data structure:
class Node:
def __init__ (self,data):
self.data = data
self.next = None
Once we have created a Node Class we can Create a Linked List Class:
class linkedList():
def __init__(self):
self.head = None
From here we can add functionality like insertion and deletion of Nodes, the following links on this page show the step-by-step processes of different functionality of a Singly Linked List.
Time Complexity for Singly-Linked List:
| Operation | Running Time (Average) | Running Time (Worst) |
|---|---|---|
| Access | O (n) | O (n) |
| Search | O (n) | O (n) |
| Insertion | O (1) | O (1) |
| Deletion | O (1) | O (1) |
Remove Duplicates of Singly Linked Lists
Coming Soon:
- Check if Linked list is a Palindrome
- Sum two Lists
Doubly Linked Lists:
For a Doubly Linked List we need to adjust the Node Class to include Previous
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
From here we can add functionality like we did in Single Linked List
Time Complexity for Doubly-Linked List:
| Operation | Running Time (Average) | Running Time (Worst) |
|---|---|---|
| Access | O (n) | O (n) |
| Search | O (n) | O (n) |
| Insertion | O (1) | O (1) |
| Deletion | O (1) | O (1) |
Doubly Linked Lists Add Node Before and After
Doubly Linked Lists Append and Prepend
Doubly Linked Lists Delete Node
Coming Soon:
- Pairs with Sum
- Remove Duplicates
- Reverse list
Circular Linked Lists:
For a Circular Linked List we can use the same Node Class that we used in Single Linked List
Circular Linked Lists Insertion