Singly Linked List

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).

Singly Linked List

• A singly linked list is a chained series of nodes in which each node is connected to the next by a pointer.

• Every linked list has a head, which is the first node of the linked list.

• 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):
        self.head = None

• Head is None initially since the Linked List has no elements.

• We can create a new linked LL list by simply writing:

LL = LinkedList()

Singly Linked List Operations

Display Linked List

• 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):
        if(self.head):
            temp_node = self.head
            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:
            print("\nEmpty Linked List!")

#Output: 18 -> 25 -> 14

Insert Element at the Beginning

• First, check whether the Linked List already exists or not.

• 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):
        if(self.head):
            new_node.next = self.head
            self.head = new_node
        else:
            self.head = new_node

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):
        if(self.head):
            last_node = self.head
            while(last_node.next != None):
                last_node = last_node.next
            last_node.next = new_node
        else:
            self.head = new_node

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(self.head):
				if(n == 1):
						self.insert_beg(new_node)
				else:
						n = n - 1
						temp_node = self.head
						while(n>1):
								temp_node = temp_node.next
								n = n - 1
						new_node.next = temp_node.next
						temp_node.next = new_node
		else:
				print("\nEmpty Linked List!")

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):
        if(self.head):
            self.head = self.head.next
        else:
            print("\nEmpy Linked List!")

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):
        if(self.head):
            if(self.head.next == None):
                self.head = None
            else:
                temp_node = self.head
                while(temp_node.next.next != None):
                    temp_node = temp_node.next
                temp_node.next = None
        else:
            print("\nEmpy Linked List!")

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(self.head):
				if(n == 1):
						self.delete_beg()
				else:
						del_next_node = self.head
						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:
				print("\nEmpty Linked List!")

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):
		if(self.head):
				if(self.head.data == val):
						self.delete_beg()
				else:
						flag = False
						del_next_node = self.head
						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):
								print("\nValue not found in linked list!")
						else:
								del_next_node.next = del_next_node.next.next
		else:
				print("\nEmpty Linked List!")

Singly Linked List Implementation

• 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

class LinkedList:
	def __init__(self):
		self.head = None

	def display(self):
		if(self.head):
			temp_node = self.head
			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:
			print("\nEmpty Linked List!")

	def insert_beg(self, new_node):
		if(self.head):
			new_node.next = self.head
			self.head = new_node
		else:
			self.head = new_node

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

	def insert_nth(self, n, new_node):
		if(self.head):
			if(n == 1):
				self.insert_beg(new_node)
			else:
				n = n - 1
				temp_node = self.head
				while(n>1):
					temp_node = temp_node.next
					n = n - 1
				new_node.next = temp_node.next
				temp_node.next = new_node
		else:
			print("\nEmpty Linked List!")

	def delete_beg(self):
		if(self.head):
			self.head = self.head.next
		else:
			print("\nEmpty Linked List!")

	def delete_end(self):
		if(self.head):
			if(self.head.next == None):
				self.head = None
			else:
				temp_node = self.head
				while(temp_node.next.next != None):
					temp_node = temp_node.next
				temp_node.next = None
		else:
			print("\nEmpty Linked List!")

	def delete_nth(self, n):
		if(self.head):
			if(n == 1):
				self.delete_beg()
			else:
				del_next_node = self.head
				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:
			print("\nEmpty Linked List!")

	def delete_val(self, val):
		if(self.head):
			if(self.head.data == val):
				self.delete_beg()
			else:
				flag = False
				del_next_node = self.head
				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):
					print("\nValue not found in linked list!")
				else:
					del_next_node.next = del_next_node.next.next
		else:
			print("\nEmpty Linked List!")

	
   
LL = LinkedList()

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!")

Problems related to Linked Lists

• Convert Binary Number in a Linked List to Integer

• Merge In Between Linked Lists

• Middle of the Linked List

• Delete Node in a Linked List

• Reverse Linked List (Advanced)

• Swapping Nodes in a Linked List

• Merge Two Sorted Lists

• Odd Even Linked List

• Partition List

• Palindrome Linked List

• Remove Linked List Elements