# Linked List

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.

### Table of contents

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 point to `null`

.

## Declaration of type node for Linked List

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.

## Python

```
class Node:
def __init__(self, data):
self.data = data
self.next = None
```

## JavaScript

```
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
```

## Traversing the Linked List

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.

## Python

```
def traverse(self):
if self.head:
temp = self.head
while temp is not None:
print(temp.data)
temp = temp.next
else:
print(None)
```

## JavaScript

```
traverse() {
if (this.head) {
let temp = this.head;
while (temp != null) {
console.log(temp.data);
temp = temp.next;
}
} else {
console.log(null);
}
}
```

## Length of a Linked List

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.

## Python

```
def length(self):
count = 0
temp = self.head
while temp:
temp = temp.next
count += 1
return count
```

## JavaScript

```
length() {
let count = 0;
let temp = this.head;
while (temp) {
temp = temp.next;
count += 1;
}
return count;
}
```

## Insertion in a Linked List

Insertion in a Linked List can be done in following three ways:

- Insertion of new node at the begining
- Insertion of new node at the end
- Insertion of new node at given position (middle or some random location)

### Insertion at the begining of the Linked List

While inserting a node at the begining position, two situation may arise:

**Insertion when Linked List is emtpy:**In this case we can simply create a new node and put the value in data part and null into the next part (which is already done in Class Node constructor) then assign it to the head.**Insertion when Linked List is not empty:**In this case create a new node, add value into the data part and assign the node pointed pointed by head to next of newly created node and then head will now point to new node.

## Python

```
def insert_at_start(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
```

## JavaScript

```
insertAtStart(data) {
const newNode = new Node(data);
newNode.next = this.head;
this.head = newNode;
}
```

### Insertion at the end of the Linked List

While inserting a node at the end position, two situation may arise:

**Insertion when Linked List is emtpy:**In this case we can simply create a new node and put the value in data part and null into the next part (which is already done in Class Node constructor) then assign it to the head.**Insertion when Linked List is not empty:**In this case create a new node, and then traverse till the end of the Linked List then add the new node in the next part of last node and put null into the next part because it is the last node now.

## Python

```
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
```

## JavaScript

```
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;
}
}
```

### Insertion at given position in the Linked List

While inserting at any given position following 3 situation may arise based on user input:

**Insertion at the begining:**In this case, simply call the function used to insert at begining.**Insertion at the end:**In this case, simply call the function used to insert at the end.**Insertion at any random position:**In this case, use a temporary variable and initialize with the head pointer traverse till the`given position - 1`

and then insert the new node by adjusting the next pointers.

## Python

```
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
```

## JavaScript

```
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;
}
}
}
```

## Deletion in a Linked List

Same as insertion deletion in a Linked List can be done in 3 ways:

- Deletion of a node from the begining
- Deletion of a node from the end
- Deletion of a node from given position (middle or some random location)

### Deletion from the begining of the Linked List

While deleting a node at the from begining, two situation may arise:

**Deletion when Linked List is emtpy:**When Linked List is empty throw an error that Linked List is empty.**Deletion when Linked List is not empty:**When Linked List is not empty simply shift the head pointer to the next element. For languages like Python, Java etc. which have in built mechanism for garbage collection, can remove the deleted node itself but in case of languages like C or C++ we have to point that node and remove it manually.

## Python

```
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')
```

## JavaScript

```
deleteFromStart() {
if (this.head) {
const data = this.head.data;
this.head = this.head.next;
return data;
} else {
throw "Empty linked list";
}
}
```

### Deletion from the end of the Linked List

While deleting a node at the from the end, two situation may arise:

**Deletion when Linked List is emtpy:**When Linked List is empty throw an error that Linked List is empty.**Deletion when Linked List is not empty:**When Linked List is not empty traverse the linked list till the second last element and then put`null`

into the next part of this node so that its link with last element can broken. For languages like Python, Java etc. which have in built mechanism for garbage collection, can remove the deleted node itself but in case of languages like C or C++ we have to point that node and remove it manually.

## Python

```
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')
```

## JavaScript

```
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";
}
}
```

### Deletion from given position in the Linked List

While deleting at any given position following 3 situation may arise based on user input:

**Deletion from the begining:**In this case, simply call the function used to delete from begining.**Deletion from the end:**In this case, simply call the function used to delete from the end.**Deletion from any random position:**In this case, use two temporary variable and initialize with the head pointer traverse one pointer till the`given position`

and the other till`given position - 1`

and then delete that node and then adjust the pointers. For languages like Python, Java etc. which have in built mechanism for garbage collection, can remove the deleted node itself but in case of languages like C or C++ we have to point that node and remove it manually.

## Python

```
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
```

## JavaScript

```
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 Linked List

Implementation of a singly linked list with all the function combined with output.

## Python

```
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()
```

## JavaScript

```
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
```