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
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 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 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, 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 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, 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 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 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, declare 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 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 visual
Data structures and Java collections