What are the Application Of Linked List

What are the Application Of Linked List

24 mins readComment
clickHere
Updated on Jan 25, 2024 15:00 IST

Have you ever wondered about the versatile applications of linked lists? These dynamic data structures are pivotal in creating efficient algorithms and complex data management systems, excelling in tasks requiring frequent insertions and deletions, such as implementing abstract data types like queues, stacks, and graphs.Let us understand more!

In computer programming, there are a wide variety of data structures that have their own unique set of properties and offer specialised ways to handle data. One such data structure is the Linked List. In this article, we will explore various use cases of a linked list in the context of programming and real-world problem-solving.

 

Application of Linked list in Computer Science

Below is a list of applications of linked list in the world of computer science

  1. Representation of Polynomials
  2. Arithmetic operations on Polynomials
  3. Addition of Long Positive integers
  4. Implementation of Queue Data structure
  5. Implementation of Stack Data structure
  6. Representation Adjacency List

Let’s take a look at each one of them in detail.

Representation of Polynomials

Polynomials are algebraic expressions that contain coefficients and variables. Linked lists can be used to represent polynomials in computer programs. For instance, to represent a polynomial like 3x^2 + 2x + 5 we can use the below reference image of a linked list.

 

Considering the same polynomial 3x^2 + 2x + 5. This polynomial can be represented as following in a linked list:

3x^2 (coefficient = 3, exponent = 2)

2x^1 (coefficient = 2, exponent = 1)

5x^0 (coefficient = 5, exponent = 0)

Understanding Variables in Java
Understanding Variables in Java
Have you ever wondered how data is stored and manipulated in Java programs? Variables in Java are the answer, acting as containers for data values. Each variable is defined with...read more

Variables in C Programming: Types, Scope, and Lifetime
Variables in C Programming: Types, Scope, and Lifetime
Variables in C Programming are a container to hold the value of a data type. They help the compiler to create memory space for the type of Variable. Each variable...read more

Variables in Python
Variables in Python
In this article, we will discuss variables in python, how to name them and how to work with the variables.

Python Program to represent Polynomials

Now, to represent the above polynomial through a linked list, take a look at the Python code below.


 
# Node class representing a term in the polynomial
class Node:
def __init__(self, coefficient, exponent):
# Coefficient of the term
self.coefficient = coefficient
# Exponent of the term
self.exponent = exponent
# Reference to the next term in the polynomial
self.next = None
# Polynomial class to manage the linked list of terms
class Polynomial:
def __init__(self):
# Initialize the head of the linked list
self.head = None
# Method to add a new term to the polynomial
def add_term(self, coefficient, exponent):
# Create a new term node
new_term = Node(coefficient, exponent)
# If the polynomial is empty, set the new term as the head
if not self.head:
self.head = new_term
else:
# Traverse to the end of the list
current = self.head
while current.next:
current = current.next
# Add the new term at the end
current.next = new_term
# Method to display the polynomial
def display(self):
current = self.head
# String to store the polynomial representation
polynomial_str = ""
while current:
# Check if the term is non-zero
if current.coefficient != 0:
if current.exponent == 0:
# Append constant term
polynomial_str += str(current.coefficient)
else:
# Append other terms
polynomial_str += str(current.coefficient) + "x^" + str(current.exponent)
if current.next and current.next.coefficient > = 0:
# Add '+' between terms if needed
polynomial_str += " + "
current = current.next
# Print the polynomial representation
print(polynomial_str)
# Create a polynomial object
poly = Polynomial()
# Add terms to the polynomial
poly.add_term(3, 2) # Add term 3x^2
poly.add_term(2, 1) # Add term 2x^1
poly.add_term(5, 0) # Add term 5x^0
# Display the polynomial
poly.display()
Copy code

Output

3x^2 + 2x^1 + 5

Arithmetic operations on Polynomials

To perform operations like addition, subtraction, multiplication and division among polynomials, we can also make use of a Linked list data structure.

Python Program to Add Polynomials


 
class Node:
def __init__(self, coef=0, exp=0):
# Coefficient of the term
self.coef = coef
# Exponent of the term
self.exp = exp
# Reference to the next
# term in the polynomial
self.next = None
class Polynomial:
def __init__(self):
# Initialize the head
# of the linked list
self.head = None
# Method to add a new term
# to the polynomial
def add_term(self, coef, exp):
# Create a new term node
new_term = Node(coef, exp)
# If the polynomial is empty,
# set the new term as the head
if not self.head:
self.head = new_term
else:
current = self.head
# Traverse to the end of the list
while current.next:
current = current.next
# Add the new term at the end
current.next = new_term
# Method to display the polynomial
def display(self):
current = self.head
# String to store the
# polynomial representation
polynomial_str = ""
while current:
# Check if the term is non-zero
if current.coef != 0:
if current.exp == 0:
# Append constant term
polynomial_str += str(current.coef)
else:
# Append other terms
polynomial_str += str(current.coef) + "x^" + str(current.exp)
if current.next and current.next.coef > = 0:
# Add '+' between terms if needed
polynomial_str += " + "
current = current.next
# Print the polynomial representation
print(polynomial_str)
# Method to add two polynomials
def add(self, poly):
result = Polynomial()
current1 = self.head
current2 = poly.head
while current1 and current2:
# If exponent of current1 is greater
if current1.exp > current2.exp:
result.add_term(current1.coef, current1.exp)
current1 = current1.next
# If exponent of current2 is greater
elif current1.exp < current2.exp:
result.add_term(current2.coef, current2.exp)
current2 = current2.next
else:
# If exponents are equal
# Add coefficients
new_coef = current1.coef + current2.coef
result.add_term(new_coef, current1.exp)
current1 = current1.next
current2 = current2.next
# Append remaining terms if any
while current1:
result.add_term(current1.coef, current1.exp)
current1 = current1.next
while current2:
result.add_term(current2.coef, current2.exp)
current2 = current2.next
return result
# Create first polynomial 3x^2 + 2x + 5
poly1 = Polynomial()
poly1.add_term(3, 2)
poly1.add_term(2, 1)
poly1.add_term(5, 0)
# Create second polynomial 2x^2 - 4x - 1
poly2 = Polynomial()
poly2.add_term(2, 2)
poly2.add_term(-4, 1)
poly2.add_term(-1, 0)
# Perform addition
print("Addition:")
result_add = poly1.add(poly2)
result_add.display()
Copy code

Output

Addition:
5x^2-2x^1 + 4

In the above code, we have generated two polynomials poly1 that is equal to 3x^2 + 2x + 5 and poly2 that is equal to 2x^2 - 4x - 1. When we add these to the polynomial we get a new polynomial equal to 5x^2-2x^1 + 4

Python program to Subtract polynomials


 
class Node:
def __init__(self, coef=0, exp=0):
# Coefficient of the term
self.coef = coef
# Exponent of the term
self.exp = exp
# Reference to the next
# term in the polynomial
self.next = None
class Polynomial:
def __init__(self):
# Initialize the head
# of the linked list
self.head = None
# Method to add a new term
# to the polynomial
def add_term(self, coef, exp):
# Create a new term node
new_term = Node(coef, exp)
# If the polynomial is empty,
# set the new term as the head
if not self.head:
self.head = new_term
else:
current = self.head
# Traverse to the end of the list
while current.next:
current = current.next
# Add the new term at the end
current.next = new_term
# Method to display the polynomial
def display(self):
current = self.head
# String to store the
# polynomial representation
polynomial_str = ""
while current:
# Check if the term is non-zero
if current.coef != 0:
if current.exp == 0:
# Append constant term
polynomial_str += str(current.coef)
else:
# Append other terms
polynomial_str += str(current.coef) + "x^" + str(current.exp)
if current.next and current.next.coef > = 0:
# Add '+' between terms if needed
polynomial_str += " + "
current = current.next
# Print the polynomial representation
print(polynomial_str)
# Method to subtract two polynomials
def subtract(self, poly):
result = Polynomial()
current1 = self.head
current2 = poly.head
while current1 and current2:
# If exponent of current1 is greater
if current1.exp > current2.exp:
result.add_term(current1.coef, current1.exp)
current1 = current1.next
# If exponent of current2 is greater
elif current1.exp < current2.exp:
result.add_term(-current2.coef, current2.exp)
current2 = current2.next
else:
# If exponents are equal
# Subtract coefficients
new_coef = current1.coef - current2.coef
result.add_term(new_coef, current1.exp)
current1 = current1.next
current2 = current2.next
# Append remaining terms if any
while current1:
result.add_term(current1.coef, current1.exp)
current1 = current1.next
while current2:
result.add_term(-current2.coef, current2.exp)
current2 = current2.next
return result
# Create first polynomial 3x^2 + 2x + 5
poly1 = Polynomial()
poly1.add_term(3, 2)
poly1.add_term(2, 1)
poly1.add_term(5, 0)
# Create second polynomial 2x^2 - 4x - 1
poly2 = Polynomial()
poly2.add_term(2, 2)
poly2.add_term(-4, 1)
poly2.add_term(-1, 0)
# Perform subtraction
print("\nSubtraction:")
result_subtract = poly1.subtract(poly2)
result_subtract.display()
Copy code

Output

Subtraction:
1x^2 + 6x^1 + 6

In the above code, we have generated two polynomials poly1 that is equal to 3x^2 + 2x + 5 and poly2 that is equal to 2x^2 - 4x - 1. When we subtract these from to polynomial, we get a new polynomial equal to 1x^2 + 6x^1 + 6

Python program to multiply Polynomials.


 
class Node:
def __init__(self, coef=0, exp=0):
# Coefficient of the term
self.coef = coef
# Exponent of the term
self.exp = exp
# Reference to the next
# term in the polynomial
self.next = None
class Polynomial:
def __init__(self):
# Initialize the head
# of the linked list
self.head = None
# Method to add a new term
# to the polynomial
def add_term(self, coef, exp):
# Create a new term node
new_term = Node(coef, exp)
# If the polynomial is empty,
# set the new term as the head
if not self.head:
self.head = new_term
else:
current = self.head
# Traverse to the end of the list
while current.next:
current = current.next
# Add the new term at the end
current.next = new_term
# Method to display the polynomial
def display(self):
current = self.head
# String to store the
# polynomial representation
polynomial_str = ""
while current:
# Check if the term is non-zero
if current.coef != 0:
if current.exp == 0:
# Append constant term
polynomial_str += str(current.coef)
else:
# Append other terms
polynomial_str += str(current.coef) + "x^" + str(current.exp)
if current.next and current.next.coef > = 0:
# Add '+' between terms if needed
polynomial_str += " + "
current = current.next
# Print the polynomial representation
print(polynomial_str)
# Method to multiply two polynomials
def multiply(self, poly):
result = Polynomial()
current1 = self.head
while current1:
current2 = poly.head
while current2:
# Multiply coefficients
new_coef = current1.coef * current2.coef
# Add exponents
new_exp = current1.exp + current2.exp
result.add_term(new_coef, new_exp)
current2 = current2.next
current1 = current1.next
return result
# Create first polynomial 3x^2 + 2x + 5
poly1 = Polynomial()
poly1.add_term(3, 2)
poly1.add_term(2, 1)
poly1.add_term(5, 0)
# Create second polynomial 2x^2 - 4x - 1
poly2 = Polynomial()
poly2.add_term(2, 2)
poly2.add_term(-4, 1)
poly2.add_term(-1, 0)
# Perform multiplication
print("\nMultiplication(non-simplified):")
result_multiply = poly1.multiply(poly2)
result_multiply.display()
Copy code

Output

Multiplication(non-simplified):
6x^4-12x^3-3x^2 + 4x^3-8x^2-2x^1 + 10x^2-20x^1-5

In the above code, we have generated two polynomials poly1 that is equal to 3x^2 + 2x + 5 and poly2 that is equal to 2x^2 - 4x - 1. When we multiply these to polynomial, we get a new polynomial equal to 6x^4-12x^3-3x^2 + 4x^3-8x^2-2x^1 + 10x^2-20x^1-5 that, when simplified, can be written as 6x^4-8x^3-21x^2+18x+5.

Python program to Divide Polynomials


 
class Node:
def __init__(self, coef=0, exp=0):
# Coefficient of the term
self.coef = coef
# Exponent of the term
self.exp = exp
# Reference to the next
# term in the polynomial
self.next = None
class Polynomial:
def __init__(self):
# Initialize the head
# of the linked list
self.head = None
# Method to add a new term
# to the polynomial
def add_term(self, coef, exp):
# Create a new term node
new_term = Node(coef, exp)
# If the polynomial is empty,
# set the new term as the head
if not self.head:
self.head = new_term
else:
current = self.head
# Traverse to the end of the list
while current.next:
current = current.next
# Add the new term at the end
current.next = new_term
# Method to display the polynomial
def display(self):
current = self.head
# String to store the
# polynomial representation
polynomial_str = ""
while current:
# Check if the term is non-zero
if current.coef != 0:
if current.exp == 0:
# Append constant term
polynomial_str += str(current.coef)
else:
# Append other terms
polynomial_str += str(current.coef) + "x^" + str(current.exp)
if current.next and current.next.coef > = 0:
# Add '+' between terms if needed
polynomial_str += " + "
current = current.next
# Print the polynomial representation
print(polynomial_str)
# Method to subtract two polynomials
def subtract(self, poly):
result = Polynomial()
current1 = self.head
current2 = poly.head
while current1 and current2:
# If exponent of current1 is greater
if current1.exp > current2.exp:
result.add_term(current1.coef, current1.exp)
current1 = current1.next
# If exponent of current2 is greater
elif current1.exp < current2.exp:
result.add_term(-current2.coef, current2.exp)
current2 = current2.next
else:
# If exponents are equal
# Subtract coefficients
new_coef = current1.coef - current2.coef
result.add_term(new_coef, current1.exp)
current1 = current1.next
current2 = current2.next
# Append remaining terms if any
while current1:
result.add_term(current1.coef, current1.exp)
current1 = current1.next
while current2:
result.add_term(-current2.coef, current2.exp)
current2 = current2.next
return result
# Method to multiply two polynomials
def multiply(self, poly):
result = Polynomial()
current1 = self.head
while current1:
current2 = poly.head
while current2:
# Multiply coefficients
new_coef = current1.coef * current2.coef
# Add exponents
new_exp = current1.exp + current2.exp
result.add_term(new_coef, new_exp)
current2 = current2.next
current1 = current1.next
return result
# Method to divide two polynomials
def divide(self, poly):
# Quotient polynomial
quotient = Polynomial()
# Remainder polynomial
remainder = Polynomial()
# Current node of the dividend polynomial
current1 = self.head
while current1:
# Current node of the
# divisor polynomial
current2 = poly.head
# Temporary polynomial to
# hold intermediate division results
temp = Polynomial()
# Initialize temp with the current term of dividend
temp.add_term(current1.coef, current1.exp)
while current2:
# Coefficient division
new_coef = current1.coef // current2.coef
# Exponent subtraction
new_exp = current1.exp - current2.exp
# Temporary polynomial to
# hold the term for subtraction
temp2 = Polynomial()
# Initialize temp2 with the term for subtraction
temp2.add_term(new_coef, new_exp)
# Subtract (temp2 * divisor) from temp
temp = temp.subtract(temp2.multiply(poly))
# Move to the next term in the divisor
current2 = current2.next
# Add the new term to the quotient
quotient.add_term(new_coef, new_exp)
# Assign the remainder as the
# result of the last subtraction
remainder = temp
# Move to the next term in the dividend
current1 = current1.next
# Return the quotient and
# remainder polynomials
return quotient, remainder
# Create first polynomial 3x^2 + 2x + 5
poly1 = Polynomial()
poly1.add_term(3, 2)
poly1.add_term(2, 1)
poly1.add_term(5, 0)
# Create second polynomial 2x^2 - 4x - 1
poly2 = Polynomial()
poly2.add_term(2, 2)
poly2.add_term(-4, 1)
poly2.add_term(-1, 0)
# Perform division
print("\nDivision - Quotient:")
result_quotient, result_remainder = poly1.divide(poly2)
result_quotient.display()
print("\nDivision - Remainder:")
result_remainder.display()
Copy code

Output

Division - Quotient:
-3x^2-2x^1-5

Division - Remainder:
10x^2-16x^1-12 + 6x^-1 + 2x^-2

In the above code, we have generated two polynomials poly1 that is equal to 3x^2 + 2x + 5 and poly2 that is equal to 2x^2 - 4x - 1. When we divide the first polynomial with the second one, we get a new quotient polynomial equal to -3x^2-2x^1-5 and the remainder polynomial equal to 10x^2-16x^1-12 + 6x^-1 + 2x^-2.

Addition of Long Positive Integers

In programming, a long positive integer refers to an integer that can have variable size, representing very large whole numbers. 

Look at the Python program below to add long positive integers using Linked List.

Python program to Add Long Positive Integers


 
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert_at_head(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def display(self):
current = self.head
while current:
print(current.data, end="")
current = current.next
print()
def add_long_integers(self, num1, num2):
carry = 0
self.head = None # Resetting head for the result list
while num1 is not None or num2 is not None:
digit1 = num1.data if num1 else 0
digit2 = num2.data if num2 else 0
if num1: num1 = num1.next
if num2: num2 = num2.next
total = digit1 + digit2 + carry
carry = total // 10
self.insert_at_head(total % 10)
if carry > 0:
self.insert_at_head(carry)
def insert_number(self, number):
for digit in str(number)[::-1]:
self.insert_at_head(int(digit))
# Create and insert numbers correctly
num1 = LinkedList()
num1.insert_number(954756)
num2 = LinkedList()
num2.insert_number(689347)
# Display the numbers to be added
print("First number:")
num1.display()
print("Second number:")
num2.display()
# Calculate the sum of the numbers and display the result
result = LinkedList()
result.add_long_integers(num1.head, num2.head)
print("Sum:")
result.display()
Copy code

Output

First number:
954756
Second number:
689347
Sum:
1401445

Note:  Python 3 eliminated the distinction between int and long types from Python 2, so integers in Python 3 automatically transition to long integers as needed, accommodating any integer size.

Implementation of Queue Data structure

A queue is a linear data structure with both ends open for operations and follows the principle of First In, First Out (FIFO).

According to the First In, First Out (FIFO) concept, the first element to enter a queue (enqueue) must also be the first element to exit the queue (dequeue). To better understand a queue, picture a queue of people waiting to get on a bus. The person in the queue will get on the bus first, and vice versa.

Take a look at the image below for reference.

 

Now that we know what a queue Data structure is let’s take a look at the implementation of a queue using a linked list in Python.

This implementation will follow the below algorithm

Algorithm

The algorithm would look like the below for the above-mentioned steps

Step 1: [START] CREATE NEW_NODE, SET FRONT = NULL, SET REAR = NULL

Step 2: SET DATA = VALUE, NEW_NODE NEXT = NULL

Step 3: If FRONT is NULL (Queue is empty)

        SET FRONT = NEW_NODE

        SET REAR = NEW_NODE

    Else

        SET REAR NEXT = NEW_NODE

        SET REAR = NEW_NODE

Step 4: EXIT

Python program to Implement Queue using Linked List


 
# initialize a node
class Node:
def __init__(self, value):
self.data = value
self.next = None
class Queue:
def __init__(self):
self.front = None
self.rear = None
def do_enqueue(self, value):
# Create a new node
new_node = Node(value)
# If queue is empty, set
# new node as front and rear
if self.front is None:
self.front = new_node
self.rear = new_node
else:
# If queue is not empty,
# add new node at the rear
self.rear.next = new_node
self.rear = new_node
def display(self):
# Display the elements in the queue
current = self.front
if current is None:
print("Queue is empty")
return
while current is not None:
print(current.data, end=" < - ")
current = current.next
print("rear")
def do_dequeue(self):
# Check if queue is empty
if self.front is None:
print("Queue is empty, cannot dequeue")
return None
else:
# dequeue the front element
temp = self.front
self.front = self.front.next
if self.front is None:
self.rear = None
return temp.data
# Example use
queue = Queue()
queue.do_enqueue(1)
queue.do_enqueue(2)
queue.do_enqueue(3)
# Display the elements in the queue
queue.display()
dequeued_value = queue.do_dequeue()
print(f"Dequeued value: {dequeued_value}")
# Display the elements after do_dequeue
queue.display()
Copy code

Output

1 <- 2 <- 3 <- rear
Dequeued value: 1
2 <- 3 <- rear

Queue Data Structure: Types, Implementation, Applications
Queue Data Structure: Types, Implementation, Applications
A queue is a linear data structure that stores the elements sequentially. It uses the FIFO approach (First In First Out) for accessing elements. Queues are typically used to manage...read more

Queue Using Linked List
Queue Using Linked List
Have you ever wondered how to efficiently manage data in a First In, First Out (FIFO) manner? Implementing a queue using a linked list in programming provides a dynamic and...read more

What is a Priority Queue?
What is a Priority Queue?
A priority queue is a type of Queue in the data structure and algorithms. It is an abstract data type and a special kind of queue. It is somehow similar...read more

A Brief Introduction to Using Queues in C++
A Brief Introduction to Using Queues in C++
Queue in C++ is used to extract or process data in a particular order and manage multiple threads. In this article, we will discuss, different types of queues in C++...read more

Queue Implementation in Python: Basic Operations and Examples
Queue Implementation in Python: Basic Operations and Examples
Learn about queues in Python, a data structure that allows you to store and manipulate collections of items in a first-in, first-out (FIFO) order. Discover the different types of queues...read more

Circular Queue in data structure
Circular Queue in data structure
This article includes working of Circular Queue in data structure and also implementation of circular queue in python and java.

Implementation of Stack Data structure

A stack is a linear data structure with one end open for operations and follows the First In, Last Out (FILO) principle.

The FILO principle states that the first element getting inside a stack(i.e., push) has to be the last element that gets out of the stack(i.e., pop). To better understand a stack, think of a stack of books placed above one another. The first book that can be taken out of the stack should be at the top and has to be placed last in that stack and vice-versa.

Take a look at the image below for reference.

 

Now that we know what a stack Data structure is, let’s take a look at the implementation of a stack using a linked list in Python.

This implementation will follow the below algorithm:

Algorithm

The algorithm would look like the below for the above-mentioned steps

Step 1: [START] Initialize Node, Create an empty stack

Step 2: Set TOP = NULL

Step 3: Define PUSH(value) to add an element

     Create a new node with the value

     If TOP is NULL

        Set TOP to the new node

    Else

         Set new node's NEXT to TOP

         Update TOP to the new node

 

Step 4: Define POP() to remove an element

     If TOP is NULL

         Display "Stack is empty"

     Else

         Set TEMP to TOP

         Move TOP to the next node

         Free memory for TEMP

Step 5: Define PEEK() to return top element

     If TOP is NULL

         Display "Stack is empty"

    Else

         Return data of TOP

Step 6: Define DISPLAY() to print stack elements

 Start from TOP

    While current node is not NULL

        Print data of current node

  Move to the next node

Step 7: [END]

Python program to Implement Stack using Linked List


 
# Node class represents each node in the linked list
class Node:
def __init__(self, data):
# Data stored in the node
self.data = data
# Pointer to the next node
self.next = None
# LinkedList class manages the linked list operations
class Stack:
def __init__(self):
# Initialize the top of the stack
self.top = None
# Method to push (add) an element onto the stack
def push(self, data):
# Create a new node
new_node = Node(data)
# Point the new node to the current top
new_node.next = self.top
# Update the top to the new node
self.top = new_node
# Method to pop (remove) an element from the stack
def pop(self):
if self.top is None:
# If stack is empty, return None
return None
else:
# Get the data from the top node
popped = self.top.data
# Move the top to the next node
self.top = self.top.next
# Return the popped element
return popped
# Method to peek at the top element without removing it
def peek(self):
if self.top is None:
# If stack is empty, return None
return None
else:
# Return the data of the top node
return self.top.data
# Method to display the elements of the stack
def display(self):
current = self.top
while current:
# Print the data of each node
print(current.data, end=" ")
current = current.next
print()
# Create a stack object
stack = Stack()
# Push elements onto the stack
stack.push(10)
stack.push(20)
stack.push(30)
# Display the elements of the stack
print("Stack elements:")
stack.display()
# Peek at the top element
print("Top element (Peek):", stack.peek())
# Pop an element from the stack
print("Popped element:", stack.pop())
# Display the elements of the stack after popping
print("Stack elements after pop:")
stack.display()
Copy code

Output

Stack elements:
30 20 10 
Top element (Peek): 30
Popped element: 30
Stack elements after pop:
20 10 

All That You Need To Know About Stack
All That You Need To Know About Stack
Author: Kanika Joshi

Representation of Adjancey List

An adjacency list is a way to represent the connections between vertices in a graph. In this type of representation, for each vertex in the graph, a list of adjacent vertices are also maintained. It's one of the two main ways to represent a graph, with the other being the adjacency matrix.

Adjacency list has 3 key components.

  • Vertices: In a graph, nodes are often referred to as vertices.
  • Edges: Connections between these vertices are known as edges. 
  • Adjacency List: For each vertex in the graph, an adjacency list holds a list of vertices adjacent to it, i.e., vertices that are connected to it by an edge.

Python program to represent Adjacency list using Linked list


 
# Node class represents each node
# in the linked list
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Graph class manages the
# adjacency list representation
class Graph:
def __init__(self, vertices):
self.V = vertices
# Initialize the adjacency
# list with V vertices
self.adj_list = [None] * self.V
# Function to add an edge between
# vertices src and dest
def add_edge(self, src, dest):
# Create a new node for the destination
new_node = Node(dest)
# Insert the new node at the beginning
# of the adjacency list for source vertex
new_node.next = self.adj_list[src]
self.adj_list[src] = new_node
# For undirected graph,
# also add an edge from dest to src
new_node = Node(src)
new_node.next = self.adj_list[dest]
self.adj_list[dest] = new_node
# Function to print the
# adjacency list representation of the graph
def print_graph(self):
for i in range(self.V):
print(f"Adjacency list of vertex {i}:")
temp = self.adj_list[i]
while temp:
print(f" - > {temp.data}", end="")
temp = temp.next
print(" \n")
# Create a graph with 4 vertices
V = 4
graph = Graph(V)
# Add edges to the graph
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 3)
# Display the adjacency list
# representation of the graph
graph.print_graph()
Copy code

Output

Adjacency list of vertex 0:
 -> 2 -> 1 

Adjacency list of vertex 1:
 -> 2 -> 0 

Adjacency list of vertex 2:
-> 3 -> 1 -> 0 

Adjacency list of vertex 3:
 -> 2 

The above code creates a graph with four vertices and implements an adjacency list using linked lists for each vertex. The add_edge method adds edges between vertices, and print_graph displays the adjacency list representation. 

Application of Linked list in Real World

Linked lists can have a wide variety of use cases in real-world applications. We will further discuss a couple of those use cases in detail in the article.

Use of Linked List in Operation System

Linked lists are widely utilised in several fundamental operating system functions, like improving system performance and resource management, as described below:

  • Process Management: The OS manages multiple processes using linked lists. A process's information is contained in each process control block (PCB), which can link to other PCBs to create a linked list. These linked lists are further used to support resource allocation, manage the process schedules, and end the process as needed.
  • File Management:  To hold data about files, including their locations, permissions, and other characteristics, directories are kept up to date as linked lists. Linked lists are used to control disc space allocation in File Allocation Tables (FAT).
  • Memory Management: Linked lists are used by OS memory management to maintain track of allocated and free memory blocks. Allocation techniques such as First, Best, and Worst Fit efficiently allocate and deallocate memory using linked lists of memory blocks.

Use of Linked List in Database System

In database systems, linked lists are essential for effective data organisation and retrieval. The following are some database areas where linked lists are used:

  • Indexing: Linked lists are used to implement indexing structures like linked lists of pointers, skip lists, or inverted lists. These structures allow quick access to the indexed data, further reducing the database query execution time and load to the database.
  • Avoid Collision:  Linked lists are used in the hash table structures used by databases to handle collisions. In Databases, there may occur an event where a bucket in the hash table may contain a linked list of entries that hash to the same index here, linked lists can be used to allow efficient handling of collisions.
  • Database Transactions: Linked lists help maintain atomicity and consistency in database transactions by making reorganising pointers or data blocks easier during transactional operations (such as insertions, deletions, and updates).

Use of Linked Lists in Music Players

For playlist management and song sequencing control, linked lists are commonly utilised in music players. Linked lists are used in music player software in the following ways:

  • Playlist Management: Linked lists are a popular way to display music playlists, with each list node representing a song. Playlist administration, maintenance, and traversal are made simple by the linked list structure.
  • Playback Control: Linked lists make handling playback functions like shuffle, repeat, and skip easier. To play songs in a different order, shuffle a playlist, for instance, by randomly rearranging the nodes in the linked list.
  • Memory management: Linked lists allow for dynamic memory allocation, which improves memory efficiency when managing playlists. No set amount of RAM is needed when songs are added or removed.

Use of Linked Lists in Web Browsers

Web browsers use linked lists to store browsing history and enable forward and backward navigation features. Web browsers use linked lists in the following ways:

  • Browsing History: Linked lists are used to keep track of web pages that have been visited over time. Every page visit is tracked as a node in the linked list, where the metadata is stored along with the URL, title, and timestamp.
  • Forward & Backward navigation: By going through the linked list in reverse order, you can enable the backward navigation capability in most browsers.  In the same way, another linked list or stack is kept up to date to record the pages viewed after going backwards to enable forward navigation.
  • Tab Management: Tabs in a browser can be managed and organized using linked lists. Users can flip among tabs in sequential order by representing each open tab as a node in a linked list.
  • Session Management: Linked lists also help with session history management, which includes the order in which pages were seen during a browsing session. This history can be used to restore sessions.

Use of Linked List in Graphics Development

Linked lists are widely used in applications that generate images or videos to manage frame data or pixel data. This has been further elaborated in the below points:

  • Pixel Data Management: Linked lists are useful for organising pixel data in image processing. Every node might stand in for a pixel, holding properties like colour. 
  • Vertex And Edge in 3D Graphics: Linked lists are used in 3D graphics to maintain geometric shape vertex and edge data. For the purpose of efficiently rendering 3D models, these lists record coordinates, normals, and connection information.
  • Texture Management: In graphics applications, texture data can be managed using linked lists. Information regarding textures, their positions, and mapping specifics may be stored by each node.

What are the Applications of DBMS?
What are the Applications of DBMS?
DBMS (Database Management System) serves as a versatile tool, revolutionizing data analytics. With its applications in data storage, retrieval, and manipulation, it empowers businesses to make informed decisions, streamline operations,...read more

What is the Full Form of DBMS?
What is the Full Form of DBMS?
DBMS is a crucial software tool that efficiently manages data, offering secure storage and easy retrieval. This system plays a vital role in modern computing, powering a wide range of...read more

What are the Advantages of DBMS?
What are the Advantages of DBMS?
The advantages of a DBMS (Database Management System) are numerous and impactful. It centralizes data storage, enhances data security and privacy, enforces data integrity, ensures efficient data access and retrieval,...read more

20+ Web Designer Interview Questions and Answers for 2024
20+ Web Designer Interview Questions and Answers for 2024
Are you a budding web designer preparing for your interviews? If you are, then you are at the right place! In this blog, you will find 20+ web designer interview...read more

Conclusion

Thus, linked lists are a fundamental data structure in computer science, widely used for their dynamic and efficient management of data. They excel in scenarios requiring frequent insertions and deletions, as they offer flexibility and memory efficiency, making them ideal for implementing abstract data types like stacks, queues, and even more complex structures like graphs and hash tables.
Contributed by: Raju Kumar

About the Author

This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio

Comments