Linked Lists
MICHEAL OGUNDERO
Introduction
A linked list is the most sought-after data structure when it comes to handling dynamic data elements.
It is a linear data structure that stores a collection of data elements dynamically.
Below is what it looks like:
Representation of a Linked List
A linked list is a chain of nodes, and each node has the following parts:
● Data – Stores the information.
● Next – Stores the address to next node.
Properties of a Linked List
● Nodes represent those data elements, and links or pointers connect each node.
● Each node consists of two fields, the information stored in a linked list and a pointer that stores the
address of its next node.
● The linked list starts with a HEAD which denotes the starting point or the memory location of first
node.
● The last node (or TAIL) contains null in its second field because it will point to no node.
● A linked list can grow and shrink its size, as per the requirement.
● It does not waste memory space
Real-life Example of Linked-List Data Structure
Below are some of the example of linked list which you must have come across:
● The back and forward button on your browser to access previous and next URL.
● Your music playlist, when your play the next song or the last played track.
● The file browser on your system which allows you to go back to the previous directory.
● Instagram stories of your peers are added as Linked List. Each tap you make on the screen allows
you to traverse through the list.
Types of Linked Lists
The linked list mainly has three types, they are:
1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List
Singly Linked List
A singly linked list is the most common type of linked list. Each node has data and an address field that
contains a reference to the next node.
Doubly Linked List
As the name suggests, the Doubly Linked Lists are two-way linked lists containing pointers to the previous
and the next node in the sequence. You can traverse forward and backward in this type of Linked List.
Circular Linked List
Circular Linked Lists traverse in the form of a circle. So, you can begin at any node and traverse the list in
either the forward or backward direction until you reach the same node again.
The last node of the Circular Linked List contains the pointer to the first node of the list. Hence, there is no
start or endpoint of this type of list.
Basic Operations on a List
● Push - insert at end
● Pop - remove at end
● Shift - remove at beginning
● Unshift - insert at beginning
● Get
● Set
● Insert
● Remove
● Reverse
The NODE Constructor
class Node:
def __init__(self, data=None, next=None):
self.data = data
self.next = next
The LINKED LIST Constructor
class LinkedList:
def __init__(self, value):
newNode = Node(value)
self.head = newNode
self.tail = newNode
self.length = 1
Push - insert at end
def insert_at_end(self, data):
newNode = Node(data)
if self.head is None:
self.head = newNode
self.tail = newNode
else:
self.tail.next = newNode
self.tail = newNode
self.length+=1
return self
N.B: Algorithms will be developed in class with all students’ involvement
Pop – remove at end
def remove_at_end(self): self.tail = pre
if self.head is None: self.tail.next = None
print("Linked list is empty") self.length-=1
return
temp = self.head if self.length == 0:
pre = self.head self.head = None
while temp.next: self.tail = None
pre=temp return temp
temp=temp.next
Print() Utility function
def print(self):
if self.head is None:
print("Linked list is empty")
return
itr = self.head
llstr = ''
while itr:
llstr += str(itr.data) + '-->'
itr = itr.next
print(llstr)
Next Class
Linked List Operations
❖ Shift
❖ Unshift
❖ Get
❖ Set
❖ Insert
❖ Remove
❖ Reverse
Please visit https://leetcode.com/ to create an account
