A Linked List or Singly Linked List is a linear data structure which collectively represents a sequence of data.
In this tutorial, we will learn about the implementation of a singly linked list and various operations on it like insertion, deletion and traversal of a Linked List.
A Linked List (also known as Singly Linked List) is a collection of nodes
in which each node is pointing to next node and last node points to
null
.
We have to create a data structure or Node which contains two part i.e, first part will contain the data to be stored and second will store address of next such node. We can create this by using user defined data type.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
Traversing means visiting all the node once i.e, we want to read all the
data available in the linked list.
We can do so by visiting all the nodes one by one and reading data
available in each node.
Simply, use a temporary node and initialize it with the head node so that
we can start with the begining of the list and then go through all the
nodes one by one till the last node is reached. And we can get the last
node by checking the next value of node i.e., if next value of node is
null
then this is the end of node.
def traverse(self):
if self.head:
temp = self.head
while temp is not None:
print(temp.data)
temp = temp.next
else:
print(None)
traverse() {
if (this.head) {
let temp = this.head;
while (temp != null) {
console.log(temp.data);
temp = temp.next;
}
} else {
console.log(null);
}
}
To find length of a linked list we can simply use a temporary variable and initialize it by assigning the head node. Now, move it to every node one by one and increase the counter variable.
def length(self):
count = 0
temp = self.head
while temp:
temp = temp.next
count += 1
return count
length() {
let count = 0;
let temp = this.head;
while (temp) {
temp = temp.next;
count += 1;
}
return count;
}
Insertion in a Linked List can be done in following three ways:
While inserting a node at the begining position, two situation may arise:
def insert_at_start(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
insertAtStart(data) {
const newNode = new Node(data);
newNode.next = this.head;
this.head = newNode;
}
While inserting a node at the end position, two situation may arise:
def insert_at_end(self, data):
new_node = Node(data)
if self.head:
temp = self.head
while temp.next:
temp = temp.next
temp.next = new_node
else:
self.head = new_node
insertAtEnd(data) {
const newNode = new Node(data);
if (this.head) {
let temp = this.head;
while (temp.next) {
temp = temp.next;
}
temp.next = newNode;
} else {
this.head = newNode;
}
}
While inserting at any given position following 3 situation may arise based on user input:
given position - 1
and then insert
the new node by adjusting the next pointers.
def insert_at_position(self, pos, data):
if pos < 0 or pos >= self.length():
raise 'Enter a valid postion'
else:
if pos == 0:
self.insert_at_start(data)
elif pos == self.length()-1:
self.insert_at_end(data)
else:
temp = self.head
for _ in range(pos-1):
temp = temp.next
new_node = Node(data)
new_node.next = temp.next
temp.next = new_node
insertAtPosition(pos, data) {
if (pos < 0 || pos >= this.length()) {
throw "Enter a valid position";
} else {
if (pos === 0) {
this.insertAtStart(data);
} else if (pos === this.length() - 1) {
this.insertAtEnd(data);
} else {
let temp = this.head;
for (let i = 0; i < pos; i++) {
temp = temp.next;
}
let newNode = new Node(data);
newNode.next = temp.next;
temp.next = newNode;
}
}
}
Same as insertion deletion in a Linked List can be done in 3 ways:
While deleting a node at the from begining, two situation may arise:
def delete_from_start(self):
if self.head:
data = self.head.data
self.head = self.head.next
return data
else:
raise Exception('Empty linked list')
deleteFromStart() {
if (this.head) {
const data = this.head.data;
this.head = this.head.next;
return data;
} else {
throw "Empty linked list";
}
}
While deleting a node at the from the end, two situation may arise:
null
into the next part of
this node so that its link with last element can broken. def delete_from_end(self):
if self.head:
current = self.head
previous = self.head
while current.next != None:
previous = current
current = current.next
previous.next = None
return current.data
else:
raise Exception('Empty linked list')
deleteFromEnd() {
if (this.head) {
let current = this.head;
let previous = this.head;
while (current.next != null) {
previous = current;
current = current.next;
}
previous.next = null;
return current.data;
} else {
throw "Empty linked list";
}
}
While deleting at any given position following 3 situation may arise based on user input:
given position
and the
other till given position - 1
and then
delete that node and then adjust the pointers. def delete_at_position(self, pos):
current = self.head
previous = self.head
if pos < 0 or pos >= self.length():
raise 'Enter a valid postion'
else:
if pos == 0:
return self.delete_from_start()
elif pos == self.length()-1:
return self.delete_from_end()
else:
for _ in range(pos):
previous = current
current = current.next
data = current.data
previous.next = current.next
return data
deleteAtPosition(pos) {
let current = this.head;
let previous = this.head;
if (pos < 0 || pos >= this.length()) {
throw "Enter a valid position";
} else {
if (pos === 0) {
return this.deleteFromStart();
} else if (pos === this.length() - 1) {
return this.deleteFromEnd();
} else {
for (let i = 0; i < pos; i++) {
previous = current;
current = current.next;
}
let data = current.data;
previous.next = current.next;
return data;
}
}
}
Implementation of a singly linked list with all the function combined with output.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert_at_start(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def insert_at_end(self, data):
new_node = Node(data)
if self.head:
temp = self.head
while temp.next:
temp = temp.next
temp.next = new_node
else:
self.head = new_node
def insert_at_position(self, pos, data):
if pos < 0 or pos >= self.length():
raise 'Enter a valid postion'
else:
if pos == 0:
self.insert_at_start(data)
elif pos == self.length()-1:
self.insert_at_end(data)
else:
temp = self.head
for _ in range(pos-1):
temp = temp.next
new_node = Node(data)
new_node.next = temp.next
temp.next = new_node
def delete_from_start(self):
if self.head:
data = self.head.data
self.head = self.head.next
return data
else:
raise Exception('Empty linked list')
def delete_from_end(self):
if self.head:
current = self.head
previous = self.head
while current.next != None:
previous = current
current = current.next
previous.next = None
return current.data
else:
raise Exception('Empty linked list')
def delete_at_position(self, pos):
current = self.head
previous = self.head
if pos < 0 or pos >= self.length():
raise 'Enter a valid postion'
else:
if pos == 0:
return self.delete_from_start()
elif pos == self.length()-1:
return self.delete_from_end()
else:
for _ in range(pos):
previous = current
current = current.next
data = current.data
previous.next = current.next
return data
def get_first(self):
if self.head:
return self.head.data
else:
raise Exception('Linked List is empty')
def get_last(self):
if self.head:
current = self.head
while current.next != None:
current = current.next
return current.data
else:
raise Exception('Linked List is empty')
def get_at_position(self, pos):
if pos < 0 or pos >= self.length():
raise Exception('Linked List is empty')
current = self.head
for _ in range(pos):
current = current.next
return current.data
def traverse(self):
if self.head:
temp = self.head
while temp is not None:
print(temp.data)
temp = temp.next
else:
print(None)
def length(self):
count = 0
temp = self.head
while temp:
temp = temp.next
count += 1
return count
ll = LinkedList()
ll.insert_at_end(1)
ll.insert_at_end(2)
ll.insert_at_end(3)
ll.insert_at_end(4)
ll.insert_at_end(5)
ll.traverse()
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
}
insertAtStart(data) {
const newNode = new Node(data);
newNode.next = this.head;
this.head = newNode;
}
insertAtEnd(data) {
const newNode = new Node(data);
if (this.head) {
let temp = this.head;
while (temp.next) {
temp = temp.next;
}
temp.next = newNode;
} else {
this.head = newNode;
}
}
insertAtPosition(pos, data) {
if (pos < 0 || pos >= this.length()) {
throw "Enter a valid position";
} else {
if (pos === 0) {
this.insertAtStart(data);
} else if (pos === this.length() - 1) {
this.insertAtEnd(data);
} else {
let temp = this.head;
for (let i = 0; i < pos; i++) {
temp = temp.next;
}
let newNode = new Node(data);
newNode.next = temp.next;
temp.next = newNode;
}
}
}
deleteFromStart() {
if (this.head) {
const data = this.head.data;
this.head = this.head.next;
return data;
} else {
throw "Empty linked list";
}
}
deleteFromEnd() {
if (this.head) {
let current = this.head;
let previous = this.head;
while (current.next != null) {
previous = current;
current = current.next;
}
previous.next = null;
return current.data;
} else {
throw "Empty linked list";
}
}
deleteAtPosition(pos) {
let current = this.head;
let previous = this.head;
if (pos < 0 || pos >= this.length()) {
throw "Enter a valid position";
} else {
if (pos === 0) {
return this.deleteFromStart();
} else if (pos === this.length() - 1) {
return this.deleteFromEnd();
} else {
for (let i = 0; i < pos; i++) {
previous = current;
current = current.next;
}
let data = current.data;
previous.next = current.next;
return data;
}
}
}
traverse() {
if (this.head) {
let temp = this.head;
while (temp != null) {
console.log(temp.data);
temp = temp.next;
}
} else {
console.log(null);
}
}
length() {
let count = 0;
let temp = this.head;
while (temp) {
temp = temp.next;
count += 1;
}
return count;
}
}
const ll = new LinkedList();
ll.insertAtEnd(1);
ll.insertAtEnd(2);
ll.insertAtEnd(3);
ll.insertAtEnd(4);
ll.insertAtEnd(5);
ll.traverse();
Output
1 2 3 4 5
AUTHOR