Linked list data structure: A linked list is a sequence of nodes in which each node has 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.
Table of Content
Define classes
Node class has two fields: data stores the value and next is the reference to the next node. LinkList class has a variable head. head always points to the first node. Its initial value is null.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
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 16 |
class LinkNode : #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, you 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 your 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 insertFirst(self, value) : newNode = LinkNode(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 insertLast(self, value) : newNode = LinkNode(value) if self.head == None: self.head = newNode else : p = self.head while p.next != None : p = p.next p.next = newNode self.length += 1 |
Doodle
Delete by key
To delete an element by the key, assign a current node reference to the head, and declare a previous node variable to be null. Compare the current node’s value with the key. If the data is not equal to the key, assign the previous node to the current node, and current nodes points to the next node. Repeat until you find the node with the value the same as the key. Now link the previous node’s next to this node’s next. If no node is found when reach 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 |
#Delete all node founds by key, Time O(n), Space O(1) def delete (self, key) : p = self.head prev = None res = False while p != None : if p.data == key : if prev == None : self.head = p.next else : prev.next = p.next self.length -= 1 res = True prev = p p = p.next return res |
Doodle
Search by key
To search by key, assign the current 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 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) : p = self.head while p != None : if p.data == key: return p p = p.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) : p = self.head while p != None: print(str(p.data), end = ' ') p = p.next print() |
Doodle
Download Java, JavaScript and Python code
Linked list animated
Data structures and Java collections