 🔗

Tags
Data Structures
Python
Published
Jan 24, 2021
with implementation in Python!
by Ashley Titus, GDSC MCE DSA Lead

### What is a Linked List?

• Simply put, a Linked List is a linear data structure in which each element points to its neighbouring element(s).

### Node

• Each piece of data in a Linked List is stored in what is called a node.
• A node consists of two pieces of information, what data is stored in the node, and the address of the next node.
• The address is a physical space (as mentioned in the figure) in the computer's memory where the next node's data is stored.
• So logically, to access a node, we would have to have access to the pointer in the previous node.
• We represent each node as of class Node with attributes `data` and `next` (by default pointing to nothing, but usually containing the next node).
``````class Node:
def __init__(self, data):
self.data = data
self.next = None``````
• A new node with data 20 is represented by `Node(20)`.

• A singly linked list is a chained series of nodes in which each node is connected to the next by a pointer.
• The last node points to None (Python)/NULL (C/C++ etc.), which signifies that the linked list ends at that point (the last node is sometimes known as the tail of the linked list).
• To reach any node, we will have to start at the head, and then move to the succeeding nodes one by one via their pointers.
• The identifying feature of every linked list is its head. therefore every object of class `LinkedList` will have a head.
``````class LinkedList:
def __init__(self):
• Head is `None` initially since the Linked List has no elements.
• We can create a new linked `LL` list by simply writing:
``LL = LinkedList()``

• If the linked list exists:
• Create a temporary variable `temp_node` pointing at the head.
• Traverse till the temporary variable points to `None` (i.e the end of the linked list)
• In each traversal, display `temp_node.data`
• Else, the linked list does not have any elements.
``````def display(self):
while(temp_node != None):
if(temp_node.next != None):
print(temp_node.data, " -> ", end=" ")
else:
print(temp_node.data, end=" ")
temp_node = temp_node.next
else:

#Output: 18 -> 25 -> 14``````

#### Insert Element at the Beginning

• If it does exist:
• The new node points to the current head.
• Then the new node is assigned as the head.
• Else if the linked list does not exist, the new node is directly appointed as the head of the linked list.
``````def insert_beg(self, new_node):
else:

#### Insert Element at the End

• If the linked list exists:
• Create a temporary variable `last_node` pointing at the head.
• Traverse till the temporary variable points to `None` (i.e the end of the linked list)
• Point `last_node` to `new_node` (the new node already points to `None`, so that step does not have to be done explicitly).
• Else if a linked list does not exist, the new node is directly appointed as the head of the linked list.
``````def insert_end(self, new_node):
while(last_node.next != None):
last_node = last_node.next
last_node.next = new_node
else:

#### Insert Node at n'th Position

• If the linked list exists:
• If the element has to be inserted in position 1, call function `insert_beg(new_node)`.
• Else:
• Create a temporary variable `temp_node` pointing at the head.
• Traverse the temporary node till n-1 node.
• Make `new_node` point to the node after `temp_node` (i.e `temp_node.next`).
• Make `temp_node` point to `new_node` (i.e `temp_node.next`).
``````def insert_nth(self, n, new_node):
if(n == 1):
self.insert_beg(new_node)
else:
n = n - 1
while(n>1):
temp_node = temp_node.next
n = n - 1
new_node.next = temp_node.next
temp_node.next = new_node
else:

#### Delete Element at the Beginning

• If the linked list exists:
• Shift the current head to the node it is pointing to (which may be `None` if there is no next node).
• Else, there are no elements in the linked list to delete.
``````def delete_beg(self):
else:

#### Delete Element at the End

• If a linked list exists:
• Create a temporary variable `temp_node` pointing at the head.
• Traverse till the temporary variable points to the second last node.
• Point the `temp_node` to `None`.
• Else, there are no elements in the linked list to delete.
``````def delete_end(self):
else:
while(temp_node.next.next != None):
temp_node = temp_node.next
temp_node.next = None
else:

#### Delete n'th Node

• If the linked list exists:
• If the element to be deleted is the first element, follow steps in `delete_beg()`
• Else:
• Create a temporary variable `del_next_node` pointing at the head.
• Traverse the temporary variable till the n-1 node.
• Make `del_next_node` point two nodes after itself (`del_next_node.next.next`).
• Else, it is an empty linked list.
``````def delete_nth(self, n):
if(n == 1):
self.delete_beg()
else:
n = n - 1
while(n>1):
del_next_node = del_next_node.next
n = n - 1
del_next_node.next = del_next_node.next.next
else:

#### Delete Node with a Specific Value

• If the linked list exists:
• If the element to be deleted is the first element, follow steps in `delete_beg()`
• Else:
• Create a temporary variable `del_next_node` pointing at the head.
• Traverse the temporary variable till the node before the node with user input. (node before the node to be deleted).
• Make `del_next_node` point two nodes after itself (`del_next_node.next.next`).
• Else, it is an empty linked list.
``````def delete_val(self, val):
self.delete_beg()
else:
flag = False
while(del_next_node != None):
if(del_next_node.next.data == val):
flag = True
break
del_next_node = del_next_node.next
if(flag == False):
else:
del_next_node.next = del_next_node.next.next
else:

• Here's a menu-driven implementation of a singly linked list in Python!
``````class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def display(self):
while(temp_node != None):
if(temp_node.next != None):
print(temp_node.data, " -> ", end=" ")
else:
print(temp_node.data, end=" ")
temp_node = temp_node.next
else:

def insert_beg(self, new_node):
else:

def insert_end(self, new_node):
while(last_node.next != None):
last_node = last_node.next
last_node.next = new_node
else:

def insert_nth(self, n, new_node):
if(n == 1):
self.insert_beg(new_node)
else:
n = n - 1
while(n>1):
temp_node = temp_node.next
n = n - 1
new_node.next = temp_node.next
temp_node.next = new_node
else:

def delete_beg(self):
else:

def delete_end(self):
else:
while(temp_node.next.next != None):
temp_node = temp_node.next
temp_node.next = None
else:

def delete_nth(self, n):
if(n == 1):
self.delete_beg()
else:
n = n - 1
while(n>1):
del_next_node = del_next_node.next
n = n - 1
del_next_node.next = del_next_node.next.next
else:

def delete_val(self, val):
self.delete_beg()
else:
flag = False
while(del_next_node != None):
if(del_next_node.next.data == val):
flag = True
break
del_next_node = del_next_node.next
if(flag == False):
else:
del_next_node.next = del_next_node.next.next
else:

print("\n1. Insert Beginning\n2. Insert End\n3. Insert n'th\n4. Delete Beginning\n5. Delete End\n6. Delete n'th element\n7. Delete value\n8. Display\n9. Exit")
ch = 0
while(ch != 9):
ch = int(input("\nEnter choice: "))
if(ch == 1):
v = int(input("\nEnter value: "))
LL.insert_beg(Node(v))
elif(ch == 2):
v = int(input("\nEnter value: "))
LL.insert_end(Node(v))
elif(ch == 3):
v = int(input("\nEnter value: "))
n = int(input("\nEnter position: "))
LL.insert_nth(n, Node(v))
elif(ch == 4):
LL.delete_beg()
elif(ch == 5):
LL.delete_end()
elif(ch == 6):
n = int(input("\nEnter value: "))
LL.delete_nth(n)
elif(ch == 7):
val = int(input("\nEnter value: "))
LL.delete_val(val)
elif(ch == 8):
LL.display()
elif(ch == 9):
exit()
else:
print("\nInvalid choice!")``````