A linked list is a sequence of nodes in which each node has a data element and a reference to the node following it. This forms a chain link of data storage. A linked list stores its data anywhere in memory. This gives a linked list enormous flexibility to expand itself. A linked list class is implemented here so that you understand how it works internally.
Table of Content
- Map of linked list implementations
- Define classes
- Add element
- Delete by key
- Search by key
- Print elements
- Free download
Map of linked list implementations
Part 1 – Linked list implementation
Part 2 – Doubly linked list implementation
Part 3 – Ciucular linked list implementation
Define linked list class
First, we define a Node class. Node class has two fields: data and next. The data stores the value. the next is the reference to the next node. LinkList class has two variables head and length. The head always points to the first node. Its initial value is null. The length is to keep track of the number of elements in the list.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class LinkNode<T> { T data; LinkNode<T> next = null; //Constructor, Time O(1), Space O(1) public LinkNode(T value) { this.data = value; } //Override, Time O(1), Space O(1) public String toString() { return String.valueOf(data); } } public class LinkList<T> { private LinkNode<T> head = null; private int length = 0; //other methods in the class } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class LinkNode { //Constructor, Time O(1), Space O(1) constructor(value) { this.data = value; this.next = null; } //Time O(1), Space O(1) toString() { return this.data; } } class LinkList{ constructor () { this.head = null; this.length = 0; } //other methods in class } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Node : #Constructor, Time O(1), Space O(1) def __init__(self, value) : self.data = value self.next = None #Time O(1), Space O(1) def __str__(self): return str(self.data) class LinkList : def __init__ (self) : self.head = None self.length = 0 |
Add element
To add an element, we have to create the node with the value first. You can add the node at the front, anywhere in the middle, or at the end, based on the design. Here is the code to add at the front and at the end.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
//Add at the head, Time O(1), Space O(1) public void insertFirst(T value) { LinkNode<T> newNode = new LinkNode<T>(value); newNode.next = head; head = newNode; length++; } //Add at the tail, Time O(n), Space O(1), n is number of nodes in list public void insertLast(T value) { LinkNode<T> newNode = new LinkNode<>(value); if (this.head == null) this.head = newNode; else { LinkNode<T> p = head; while (p.next != null) p = p.next; p.next = newNode; } length++; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
//Add at the head, Time O(1), Space O(1) insertFirst(value) { var newNode = new LinkNode(value); newNode.next = this.head; this.head = newNode; this.length++; } //Add at the tail, Time O(n), Space O(1), n is number of nodes in list insertLast(value) { var newNode = new LinkNode(value); if (this.head == null) this.head = newNode; else { var p = this.head; while (p.next != null) p = p.next; p.next = newNode; } this.length++; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#Add at the head, Time O(1), Space O(1) def insert_first(self, value) : newNode = Node(value) newNode.next = self.head self.head = newNode self.length += 1 #Add at the tail, Time O(n), Space O(1), n is number of nodes in list def insert_last(self, value) : newNode = Node(value) if self.head == None: self.head = newNode else : curr = self.head while curr.next != None : curr = curr.next curr.next = newNode self.length += 1 |
Doodle
Delete by key
To delete an element by the key, declare a p node reference to the head, and declare a prev node to be null. The prev represents the previous node of the current node p. Compare the p node’s value with the key. If the data is not equal, assign the prev node to the p node, and the p node points to its next node. Repeat until you find the node with the value the same as the key. Now link the prev’s next to this node’s next. If no node is found when reaches the end, return null.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
//Delete all nodes found by key, Time O(n), Space O(1) public boolean delete(T key) { LinkNode<T> p = head; LinkNode<T> prev = null; boolean res = false; while (p != null) { if (p.data == key) { if (prev == null) { this.head = p.next; } else { prev.next = p.next; } this.length--; res = true; } prev = p; p = p.next; } return res; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
//Delete all nodes found by key, Time O(n), Space O(1) delete (key) { var p = this.head; var prev = null; var res = false; while (p != null) { if (p.data === key) { if (prev == null) { this.head = p.next; } else { prev.next = p.next; } this.length--; res = true; } prev = p; p = p.next; } return res; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#Delete first node found by key, Time O(n), Space O(1) def delete (self, key) : curr = self.head if self.head == None: #edge case, empty return elif self.head.data == key: #edge case, head is key self.head = self.head.next self.length -= 1 return prev = None while curr != None : if curr.data == key : prev.next = curr.next self.length -= 1 return prev = curr curr = curr.next |
Doodle
Search by key
To search by key, declare the p node reference to head. Compare the data with the key. If they are not equal, move the reference to the next node. Repeat until you find the node with a value the same as the key. Return this node. If no node is found when the reference reaches the end, return null.
Java
|
1 2 3 4 5 6 7 8 9 10 |
//Search by key, Time O(n), Space O(1) public LinkNode<T> search(T key) { LinkNode<T> p = head; while (p != null) { if (p.data == key) return p; p = p.next; } return null; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 |
//Search by key, Time O(n), Space O(1) search(key) { var p = this.head; while (p != null ) { if (p.data == key) return p; p = p.next; } return null; } |
Python
|
1 2 3 4 5 6 7 8 |
#Search by key, Time O(n), Space O(1) def search(self, key) : curr = self.head while curr != None : if curr.data == key: return curr curr = curr.next return None |
Doodle
Print elements
Starting from the head, print the value of each node. Then follow the chain of reference from link to link until reaching the end.
Java
|
1 2 3 4 5 6 7 8 9 |
//Print the list, Time O(n), Space O(1) public void print() { LinkNode<T> p = head; while (p != null) { System.out.print(p.data + " "); p = p.next; } System.out.println(); } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 |
//Print the list, Time O(n), Space O(1) print() { var p = this. head; var s = ''; while (p != null) { s += p.data + ' '; p = p.next; } console.log(s); } |
Python
|
1 2 3 4 5 6 7 |
#Print the list, Time O(n), Space O(1) def print(self) : curr = self.head while curr != None: print(str(curr.data), end = ' ') curr = curr.next print() |
Doodle
Free download
Download Linked list implementation in Java, JavaScript and Python
Download all Data Structures implementations in Java