Data Structures
Data: Raw Facts
Information: Processed data
Data Structure: Providing structure for the ‘Data’ to Convert it as ‘information’.
2 Types: 1. Linear data structure
2. Non Linear data structure (Tree, graph)
Linear data structure: Data elements arranged in a sequential order, with each element
linked to the elements before and after it.
4 Types of Linear data structure:
1. Arrays (Continuous Memory allocation)
2. Linked lists (Discontinuous Memory allocation)
3. Queues
4. Stacks
● Arrays: Data elements are stored in adjacent memory locations.
● Linked lists: A sequence of elements where each element has a reference to the next element.
● Stacks: Elements are added to the top of the stack (push) and removed from the top of the
stack(pop).
A structure that uses the last in, first out (LIFO) principle
● Queues: Elements are added from the back (enqueue) and removed from the front
(dequeue).
A structure that uses the first in, first out (FIFO) principle
Introduction to Linked Lists:
A linked list is a linear data structure where elements are stored as nodes.
o Each node consists of:
▪ data: The value of the element.
▪ next: A pointer/reference to the next node.
● Advantages:
o Dynamic size.
o Efficient insertions and deletions.
● Disadvantages:
o Sequential access (no direct access like arrays).
o Extra memory for pointers.
Types of Linked Lists
● Singly Linked List:
o Each node points to the next node, and the last node points to None.
● Doubly Linked List:
o Nodes have two pointers: next and prev for forward and backward traversal.
● Circular Linked List:
o The last node points back to the head, forming a circle.
#EXAMPLE SINGLY LINKED LIST:
class Singly:
def __init__(self, data):
self.data=data
self.next=None
def get_data(self):
return self.data
def get_next(self):
return self.next
def set_data(self, new):
self.data=new
def set_next(self, new):
self.next=new
n1=Singly(10)
n2=Singly(20)
n3=Singly(30)
n4=Singly(40)
n1.set_next(n2)
n2.set_next(n3)
n3.set_next(n4)
head=n1
pointer=head
while pointer!=None:
print(pointer.get_data() )
pointer=pointer.get_next()
#EXAMPLE Doubly/Circular LINKED LIST:
class Doubly:
def __init__(self, data):
self.prev=None
self.data=data
self.next=None
def get_prev(self):
return self.prev
def get_data(self):
return self.data
def get_next(self):
return self.next
def set_prev(self, new):
self.prev=new
def set_data(self, new):
self.data=new
def set_next(self, new):
self.next=new
n1=Doubly(10)
n2=Doubly(20)
n3=Doubly(30)
n4=Doubly(40)
n1.set_next(n2)
n2.set_prev(n1)
n2.set_next(n3)
n3.set_prev(n2)
n3.set_next(n4)
n4.set_prev(n3)
#------------------------------------------
#This is for Circular Linked List only;
#where n1 is pointing to n4 and vice versa
#n4.set_next(n1)
#n1.set_prev(n4)
#------------------------------------------------
head=n1
pointer=head
tail=n4
ptr_head=head
ptr_tail=tail
while ptr_head!=None:
print(ptr_head.get_data())
ptr_head=ptr_head.get_next()
while ptr_tail!=None:
print(ptr_tail.get_data())
ptr_tail=ptr_tail.get_prev()
#------------------------------------------
#This is for Circular Linked List only;
while True:
print(ptr_head.get_data())
ptr_head.get_next()
●
Stacks
● A stack is a LIFO (Last In, First Out) data structure.
● Operations:
o Push: Add an element to the top.
o Pop: Remove the top element.
o Peek: View the top element.
● Applications:
o Undo operations in software.
o Backtracking problems.
#Example for Stack:
class Stack:
def __init__(self):
self.st=[]
def push(self, value):
self.st.append(value)
def pop(self):
return self.st.pop()
def display(self):
print(self.st)
S=Stack()
S.push(10)
S.push(20)
S.push(30)
S.push(40)
S.display()
S.pop()
S.display()
