UNIT I : Introduction

DATA STRUCTURES AND ALGORITHMS

UNIT I : Introduction
Introduction to Data Structures: Concept of data, Data object, Data
structure, Concept of Primitive and non-primitive, linear and Nonlinear,
static and dynamic, persistent and ephemeral data structures,
Definition of ADT
Analysis of algorithm: Frequency count and its importance in analysis
of an algorithm, Time complexity & Space complexity of an algorithm
Big 'O', ‘Ω' and 'Θ' notations,
Sequential Organization: Single and multidimensional array and
address calculation.
Linked Organization: Concept of linked organization, Singly Linked List,
Doubly Linked List, Circular Linked List (Operations: Create, Display,
Search, Insert, Delete).
Case Study: Set Operation, String Operation
Linear data structure using Linked
organization

(Linked List)
Unit 1 :: Linked Organization:
Concept of linked organization,
 Singly Linked List,
Doubly Linked List,
Circular Linked List
(Operations: Create, Display, Search, Insert, Delete)

Kirti Digholkar
 Array As List Data Structure

Data
structur
es
Non Scalar
Non
Primitive/Scalar
Primitive/List
DS
DS
integer charac Linear Non
ter Float Pointer DS Linear

Linked Hash
Array Graph Tree
List table

Stack and
Queue
Further classification of Linear List

Linear
List

Restricted General
List List

Linked
Stack Queue Array List

Kirti Digholkar
 Abstract Data Type (ADT)
• Data type
• a set of objects + a set of operations
• Example: integer
• set of whole numbers
• operations: +, -, x, /
➢Abstract data type
• high-level abstractions (managing complexity through
abstraction)
• Encapsulation
Kirti Digholkar
 Encapsulation
• Operation on the ADT can only be done by calling the
appropriate function
• no mention of how the set of operations is implemented
➢The definition of the type and all operations on that type can be
localized to one section of the program
✓ If we wish to change the implementation of an ADT
• we know where to look
• by revising one small section we can be sure that there is no subtlety
elsewhere that will cause errors
✓ We can treat the ADT as a primitive type: we have no concern
with the underlying implementation
• ADT → C++: class
Kirti Digholkar

• method → C++: member function

 ADT…
 Examples
set ADT
A set of elements
Operations: union, intersection, size and complement
queue ADT
A set of sequences of elements
Operations: create empty queue, insert, examine, delete, and
destroy queue
 Two ADT’s are different if they have the same underlying model but
different operations
E.g. a different set ADT with only the union and find operations
The appropriateness of an implementation depends very much on
the operations
Kirti Digholkar
to be performed
 List Overview
• What is a list data structure and its ADT
• Array as an list
• Linked List as a list
• Why linked list ?
– Limitations of array
• Linked lists
– Abstract data type (ADT)
– Types of linked list
• Basic operations of linked list and their implementations ::
– Insert, find, delete, print, etc.
• Variations of linked lists
– Circular linked lists
– Doubly linked lists
 The List ADT
• Object :
• A sequence of zero or more elements
A1, A2, A3, … AN
• N: length of the list
• A1: first element
• AN: last element
• Ai: position i
• If N=0, then empty list
• Linearly ordered
– Ai precedes Ai+1
– Ai follows Ai-1
 List ADT :: Operations
• Display_List: print the list
• Create_Emptylist: create an empty list
• Search/Locate :locate the position of an object in a list
– list: { 34,12,_ 52, 16, 12}
– Search (52) ➔ 3
• Insert: insert an object to a list
– Before insertion list is ➔ List :: { 34,12, 52, 16, 12}
– After Insertion :: insert(x,3) → {34, 12, 52, x, 16, 12}
• Delete: delete an element from the list
– list before deletion ::List :: {34, 12, 52, 16, 12}
– List after Deletion :: Delete(52) → 34, 12, x, 16, 12
• Retrive_kth_element :: retrieve the element at a certain position
 Implementation of an ADT
• Two standard implementations for the list ADT
– Array-based
– Linked list
 Overall operations on the list:
Insertion
• Create • Insert at first
• Insertion • Insert at last
• Insert at particular position
• Deletion
Deletion
• Searching • Deletion at Front
• Display • Deletion at last
• Sorting • Deletion a particular element
• Reverse Searching :
• Linear search
• Split • Binary Search
• Merge
Display
• Forward Display
• Backward Display
 Array Implementation

• Elements are stored in contiguous array positions

 Array Implementation...
• Requires an estimate of the maximum size of the list
• Display linear
• Search linear
• RetriveKth_Element: constant
• Insert and Delete: slow
– e.g. insert at position 0 (making a new element)
• requires first pushing the entire array down one spot to make room
– e.g. delete at position 0
• requires shifting all the elements in the list up one
– On average, half of the lists needs to be moved for either
operation
 Why Linked list ?
• Limitations of array
– Dynamic vs. static data structure
• unpredictable storage requirement wastage of memory
– Operations on array vs. linked list
• Extensive manipulation of data make it slow
• Hard to implement nonlinear data structure using array.
• Tree, graph ,etc
Linked Lists
 A linked list is a linear collection of data
elements, called nodes, where the linear
order is given by means of pointers.
 Each node is divided into two parts:
➢ The first part contains the information of the
element and
➢ The second part contains the address of the next
node (link /next pointer field) in the list.
 Linked Lists
A B C 
Head

• Linked list is ordered list type.

• A linked list is a series of connected node
nodes
• Each node contains at least A
– A piece of data (any type) data pointer
– Pointer /link to the next node
in the list
• Head: pointer to the first node
• The last node links points to NULL
 Pointer Implementation (Linked List)
• Ensure that the list is not stored contiguously
– use a linked list
– a series of structures that are not necessarily adjacent in memory

▪ Each node contains the element and a pointer to a structure containing its successor
▪the last cell’s next link points to NULL
▪ Compared to the array implementation,
✓the pointer implementation uses only as much space as is needed for the elements
currently on the list
but requires space for the pointers in each cell
 A Simple Linked List C++ implementation
• Declare Node structure for the
nodes
– data: int/ char/ floating -
type
Node
– next: a pointer to the next
10
node in the list
data next

struct Node Class linked_list

{ {
int/char/float/struct data; // data Node *head;
Node* next; // pointer to next public ::
}; linked_list();
Kirti Digholkar
~ linked_list();
}
 Pointer-Based Linked Lists

Figure :: A head pointer to a list

Figure :: A lost cell

 Terminology
• Linked list a list consisting of items in which each item
knows the location of the next item.
• Node an item in a linked list.
• Each node contains a piece of list data and the location of
the next node (item).
• link (of a node) the location of the next node.
• Head node first node in a linked list
• Head pointer points to the head node
Basic Structure
 Pseudo code

• Problems:
• Create an empty list.
head = NULL;

• Determine if a list is
empty if (head == NULL)
// list is empty
 Create
void main() /* // multiple nodes
{ Node *p,* head =NULL; cout<<“\n\t How many
int i; elements”;
clrscr(); cin>> limit;
// One node creation p=head;
head = new (Node); for(i=0;i<limit;i++)
{
cin>> head->data;
p->next= new(Node);
head->next=NULL;
p=p->next;
cout<< head->data; cin>> p->data;
}
}
 Displaying the Contents of a
Linked List
Head Head

The effect of the assignment cur = cur->next

Display Linked
 Display forward
1. tempptr =headptr

2. while(tempptr not reached to end of the list)

i. Cout<< “( tempptr(dat))”;
//move tempptr to next node
ii. tempptr=tempptr-> next
End of while
End of diplay
Displaying the Contents of a Linked
List
Void display(Node *HeadD) Recursive
{ while(*HeadD!=NULL) void printR(Node *Head
{ {
if(Head!=NULL)
cout<< HeadD->data
{ printf head(data)
HeadD = HeadD->next
printR(head(next))
}
}
}
}
 Preliminaries
Head

Head

Head

Figure a) A linked list of integers; b) insertion; c) deletion

 Insert Node
• Insert at beginning
• Insert at the end
• Insert Inbetween

Kirti Digholkar
 Insertion

Nodeptr insert_S(Nodeptr
• Insertin at Head)
start {
1. t → next = Nodeptr temp = allocate
start address()
2. start = t temp->next =Head
Return start Head = temp
return Head;
}
 Insertion
Void insert_E(Node *Headt)
• Insertion at LAST
{
1. p = start
2. Repeat step 3 Node *p, *temp = allocate
address();
until p → next
NULL p =Headt;
3. p = p→ next while(p!=NULL)
4. p → next = {
getnode() p = p->next;
6. Return start }
p ->next = temp;
Kirti Digholkar
}
 Insertion
Insertion at MIDDLE / inbetween
1. Enter info of the node after which
new node to be inserted
2. Read x
3. p = start
4. Repeat step 5 until p→ info < > x
5. p = p → next
6. t→ next = p → next
7. p → next = t
8. Return
Kirti Digholkar
Void insert_Betw(Nodeptr
Head) while(temp ->data != data and temp->next
{ !=NULL)
Nodeptr tempD = allocate { tep2= temp
memory temp = temp->next
// Scan data before you if(temp->data=data)
want to insert
{ tep2->next =tempD
scan data
tempD->next=temp
If (Head = NULL)
Flag =1
{ Head -> temp
}
return Head
}
}
if(flag ==1) {no position found }
 Create a single isolated node
Create/Getnode function
1. Declare a pointer
2. Allocate a memory for single
node
3. Add data part
4. Make next pointer =NULL
Nodeptr Getnode()
{
5. Return the node
Noteptr temp
temp =allocate memory
2000
2000 Scan temp(data)
temp->next=NULL
temp
10 NULL return temp
}
 Deleting a Specified Node from a
Linked List

Figure :: Deleting a node from a linked list

Figure :: Deleting the first node

 Deletion
• Delete first node
1. x = start • Delete value
2. start = start→ next
1. Enter the info of node to be
deleted
3. free(x) 2. Read n
Delete last node 3. p = start
1. p = start 4. c = start
c = start 5. while (c → info!= n || c < >
2. while (c →next < > NULL)
NULL)
{ p=c
p=c
c = c→ next }
c = c→ next
6. p→ next = c→ next
3. p → next = c→ next 7. free ( c )
4. free ( c) 8. Return start
5. return start
Deleting a Specified Node from a
Linked List
• Deleting an interior node
prev->next=cur->next;
• Deleting the first node
head=head->next;
• Return deleted node to system
cur->next = NULL;
delete cur;
cur=NULL;
Node *reverse(Node * start)
{
Node *current ,*temp, *result;
temp=NULL;
result=NULL;
current =start; Reverse The
if(start->next==NULL)
return start; Singly Link
while(current!=NULL)
List
{
temp = current->next;
current->next = result;
result= current;
current = temp;
}
start = result;
return start;
}
Display List in reverse order

void printR(Node *head)

{
if(head != NULL)
{
printR(head->next);
printf("%d ",head->data);
}
}
 Merging two linked list
Node *Merge (Node * head1, Node *head2 ,
Node * head3)
Node * h1, *h2, h3
{
// create third list first node
head3= (Node *) malloc(sizeof (Node))
head3- >info =h1->info
head1=h1->next
head3->next =NULL
h3=head3
 Merging continued …
• Case 1
– copy all the remaining node of list one to list 3
• Case 2
– Copy the all the remaining element of list two to
list three
• Last
– Return header of list 3
 Variations of Linked Lists
• Circular linked lists
– The last node points to the first node of the list

A B C

Head

– How do we know when we have finished traversing

the list? (Tip: check if the pointer of the current
node is equal to the head.)
 Variations of Linked Lists
• Doubly linked lists
– Each node points to not only successor but the
predecessor
– There are two NULL: at the first and last nodes in
the list
– Advantage: given a node, it is easy to visit its
predecessor. Convenient to traverse lists backwards

 A B C 

Head
 Node Declaration

struct Node
{ Class DLL
int/char/float/struct data; // data {
Node *prev; // pointer to previous Node *head;
Node * next; // pointer to next public ::
}; linked_list();
~ linked_list();
}

Kirti Digholkar
Insert Beginning

Insert End
Insert in between
 Array versus Linked Lists

• Linked lists are more complex to code and manage than

arrays, but they have some distinct advantages.
– Dynamic: a linked list can easily grow and shrink in size.
• We don’t need to know how many nodes will be in the list. They are
created in memory as needed.
• In contrast, the size of a C++ array is fixed at compilation time.
– Easy and fast insertions and deletions
• To insert or delete an element in an array, we need to copy to
temporary variables to make room for new elements or close the gap
caused by deleted elements.
• With a linked list, no need to move other nodes. Only need to reset
some pointers.
Circular Linked List
 Circular Linked Lists
• In linear linked lists if a list is traversed (all the
elements visited) an external pointer to the
list must be preserved in order to be able to
reference the list again.
• Circular linked lists can be used to help the
traverse the same list again and again if
needed.
• A circular list is very similar to the linear list
where in the circular list the pointer of the last
node points not NULL but the first node.
Linked Lists

A Linear Linked List

Circular Linked Lists
 Application of Circular Linked List
1. A timesharing problem solved by the operating system.
• In this the operating system must maintain a list of
present users
• Must alternately allow each user to use a small slice
of CPU time, one user at a time.
• The operating system will pick a user, let him/her use
a small amount of CPU time
• And then move on to the next user, etc.
2. Circular linked list is the basic idea of round robin
scheduling algorithm. A circular linked list can be
effectively used to create a queue (FIFO) or a deque
(efficient insert and remove from front and back
Application of Circular Linked List
3. Multiplayer games :
• All the Players are kept in a Circular Linked List
and the pointer keeps on moving forward as a
player's chance ends.
• A jitter buffer is a type of buffer
– that takes numbered packets from a network and places
them in order, a video or audio player can play them in
order.
– Packets that are too slow (laggy) are discarded.
– This can be represented in a circular buffer, without
needing to constantly allocate and deallocate memory,
as slots can be re-used once they have been played.
 PRIMITIVE FUNCTIONS IN
CIRCULAR LISTS
• The structure definition of the circular linked
lists and the linear linked list is the same:
struct node
{
int data;
struct node *next;
};
typedef struct node *Node
 PRIMITIVE FUNCTIONS IN CIRCULAR LISTS

• Create
• Insertion (Start, In between, End )
• Deletion (Start, In between, End )
• Searching
• Display
• Sorting
• Reverse
• Split
• Merge
 Create CLL
• Allocate memory to Head node in main ;
• Head->data = - 999
• Head ->next = NULL
1. // in create function pass Head node , return type will be
void
2. Ask no of nodes to be inserted n
3. Allocate memory to to Temp , scan Head->data
4. Temp->next = Head;
5. Repeat 3 till n
void create_link(struct link *start)
{
int ch;
node = start ;
printf("\n Enter 'n' for break:");
scanf(“%d “,&ch);
while(i<ch)
{
node->next=getdata()
node=node->next;
node->next=start;
i++;
}
}
 Display
Display( Node * head)
{ p=Head ->next;
do
{
printf(p->data)
p= p->next
}while(p !=Head)
}
void insertFirst(Node * Head)
{ //create a link
Insert At First in CLL
struct node *link = (struct node*) malloc(sizeof(struct node));
Scanf(“%d”,&link->data);
if (Head->next = NULL)
{
head ->next = link;
link->next = head;
}
else
{ //point it to old first node
link->next = head->next;
head->next = link; //point first to new first node
}
}
void insertEnd(Node * Head) Insert At END in CLL
{ //create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
Scanf(“%d”,&link->data);
if (Head->next = NULL)
{
head ->next = link;
link->next = head;
}
else
{ p = head->next;
While(p->next!=Head)
p=p->next;
P->next = link;
Link->next = head
}
}
void insertINBet(Node * Head) {
{ //create a link p = head->next;
Insert
struct node *link = (struct node*) While(p->data!=n && p- in
malloc(sizeof(struct node)); >next!=Head) betwe
Scanf(“%d”,&link->data); {
p=p->next;
en in
Printf(After which to add)”;
Scanf(“%d”,&n); } CLL
if (Head->next = NULL) If(p->next ==Head)
{ printf(“data not
found”);
head ->next = link;
Else
link->next = head;
{
}
Link->next = p->next;
Else
P->next = link;
}
}
 Delete node from any where
void Delete(Node * Head)
else if(p->next ==Head &&
{ printf(“Data to be deleted”); p>data ==n )
scanf(“%d”,&n); {
p = head->next; head ->next = p->next;
Q=p; free p;
If(p==NULL) //list is empty }
while(p->data!=n && p->next!=Head) else
{ {
Q= p; q->next = p->next;
p=p->next; free p;
} }
If(p->next ==Head && p>data !=n ) }
printf(“data not found”);
With Head Node
 Node structure for polynomial
struct node
{
int coeff , expo;
struct node *next;
};
typedef struct node *Node
• Else
– p = head->next;
– Check till exponent greater than temp->exponent
– q =p // will point to previous node
– p=p->next;
– temp->next = q->next
– q->next = temp
 Display
Display( Node * head)
{ p=Head ->next;
do
{
printf(p->coeff , p->expo)
p= p->next
}while(p !=Head)
}
Application of Singly
Linked List
List Stack Example
Stack st = new Stack();
st.push(6);

top

6
List Stack Example
Stack st = new Stack();
st.push(6);
st.push(1);

top

6
List Stack Example
Stack st = new Stack();
st.push(6);
st.push(1);
st.push(7);
top 7

6
List Stack Example
Stack st = new Stack();
8 st.push(6);
st.push(1);
st.push(7);
top 7 st.push(8);

6
List Stack Example
Stack st = new Stack();
8 st.push(6);
st.push(1);
st.push(7);
top 7 st.push(8);
st.pop();

6
List Stack Example
Stack st = Stack();
st.push(6);
st.push(1);
st.push(7);
top 7 st.push(8);
st.pop();

6
 Queue Using Linked lists
78
• Each node in a dynamic data structure contains data AND a
reference to the next node.
• A queue also needs a reference to the head node AND a
reference to the tail node.
• The following diagram describes the storage of a queue called
Queue. Each node consists of data (DataItem) and a
reference (NextNode).

• The first node is accessed using the name Queue->Head.

• Its data is accessed using Queue->Head->DataItem
• The second node is accessed using Queue->Head->NextNode
• The last node is accessed using Queue->Tail
 Adding a node (Add)
79
The new node is to be added at the tail of the queue. The
reference Queue.Tail should point to the new node, and the
NextNode reference of the node previously at the tail of the
queue should point to the DataItem of the new node.
 Removing a Node
• The value of Queue.Head.DataItem is returned. A
temporary reference Temp is declared and set to point to
head node in the queue (Temp = Queue.Head).
• Queue.Head is then set to point to the second node instead
of the top node.
• The only reference to the original head node is now Temp
and the memory used by this node can then be freed.

80