CS221 Data Structure-I

S. Y. B. Tech
Trimester – II Course

SCHOOL OF COMPUTER SCIENCE AND ENGINEERING

 Linked List
Topics to be Covered
• Linked List as an ADT

• Representation of Linked List Using Sequential Organization

•Representation of Linked List Using Dynamic Organization

• Operations on Linked List

•Polynomial operations using linked list

•Circular Linked List, Doubly Linked List , Generalized

Linked List (GLL)

Case Study : Garbage Collection

DATA STRUCTURE -I UNIT-IV
 DATA STRUCTURE

LINEAR NONLINEAR

ARRAY
TREES &
LINKLIST STACK
GRAPH
QUEUE
 Linked List ADT
structure Linked List (item)
declare CREATE() -> Linked list
insert(item, linked list) -> linked list
delete(linked list) -> linked list
ISEMPS(linked list) -> boolean;
for all L ∈ Linked list, i ∈ item let
ISEMPS(CREATE) ::= true
ISEMPS(insert(i,L)) ::= false
delete(CREATE) ::= error
delete(insert(I,L)) ::= L
end Linked List
 Introduction to linked list
• Representation of simple data structures using an array and a sequential
mapping are studied.

• These representations had the property that successive nodes of the data
object were stored fixed distance apart.

• If the element aij of a table was stored at location Lij, then a i, j+1 was at the
location L ij + c for some constant c;

(BAT, CAT, EAT, FAT, HAT, JAT, LAT, MAT, OAT, PAT, RAT, SAT, TAT, VAT,
WAT)

• Disadvantage of a sequential mapping for ordered lists

– insertion and deletion of arbitrary elements become expensive.(Add
word GAT will require shifting)
 Introduction to linked list contd…
• Solution to this problem of data movement in sequential representations
is achieved by using linked representations .

• Unlike a sequential representation where successive items of a list are

located a fixed distance apart, in a linked representation these items may
be placed anywhere in memory.

• Another way of saying this is that in a sequential representation the order

of elements is the same as in the ordered list, while in a linked
representation these two sequences need not be the same.
 Introduction to linked list contd…
• To access elements in the list in the correct order, with each element we
store the address or location of the next element in that list.

• Thus, associated with each data item in a linked representation is a pointer

to the next element.

• This pointer is often referred to as a link.

• In general, a node is a collection of data, DATA1, ..., DATAn and links

LINK1, ...,LINKm. Each item in a node is called a field. A field contains
either a data item or a link.
 Linked lists
• Linked lists are appropriate when the number of data elements
to be represented in the data structure at once is unpredictable.

• Linked lists are dynamic, so the length of a list can increase or

decrease as necessary.

• Each node does not necessarily follow the previous one

physically in the memory.

• Linked lists can be maintained in sorted order by inserting or

deleting an element at the proper point in the list.
 What is Linked List?
• A linked list is an ordered collection of finite homogeneous data
elements called nodes where the linear order is maintained by means
of links or pointers.

Pointer to the
first node

Link Field/
Info/Data
Address Field
field
 Anatomy of a linked list
• A linked list consists of:
– A sequence of nodes

myList

a b c d

Each node contains a value

and a link (pointer or reference) to some other node

The last node contains a null link

The list may (or may not) have a header
 More terminology
• A node’s successor is the next node in the sequence
– The last node has no successor

• A node’s predecessor is the previous node in the sequence

– The first node has no predecessor

• A list’s length is the number of elements in it

– A list may be empty (contain no elements)
 Realization of Linked List Using Arrays
• Let L ={Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec}

• L is an ordered set

• List is stored in Data -1D array

• Elements are not stored in the same order as in the set L.

• To maintain the sequence ,second array ,Link is added

• List starts at 10th Loc
 Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec

Data Index Link

Jun 1 4
Sep 2 7
Feb 3 8
Jul 4 12
5
Dec 6 -1
Oct 7 14
Mar 8 9
Apr 9 11
Head 10 3
Jan
May 11 1
Aug 12 2
13
Nov 14 6
15
 Dynamic memory management
• In which memory resources are allocated whenever they are
needed, and freed whenever they are not necessary anymore

• Linked lists, are defined precisely in such a way as to allow for

dynamically allocating and deallocating memory, depending
on the requirements of the application.
 Pointers in C

• Declare Pointer P of type integer: Int *P;

• Allocate memory and assign its address to

P:
P = (int *) malloc ( sizeof ( int ) );
• Store value 10 in the allocated memory:
P 10
*P = 10;

Notes:
1. The new allocated memory is anonymous ( i.e. does not
have a name of its own
2. The only way we can access this location is via P.
 Pointers in C – Dynamic Memory Allocation

• But what does this complicated line do?:

P = (int *) malloc ( sizeof ( int ) ); Read This First
!!!

int Sizeof( int ): 1

But, what is this void * 3 A function that takes a primitive
in front of malloc? data type like int, float, char, etc.
Well, we do not know and just return its size in bytes!
what type of address to
return until we use void * malloc( int ): 2
malloc in our programs!! A function that takes a number
So, that’s why we cast of bytes, and dynamically allocate
void * to int * in this memory of that size in bytes,
example, since P is and finally returns its address!
declared of type int* . (in this case to P)
 Types of linked lists
• The number of pointers are maintained depending on the
requirements and usage

• Based on this ,linked list are classified into three categories.

– Singly linked lists
– Circular linked lists
– Doubly linked lists
 Empty List
• Empty Linked list is a single pointer having
the value of NULL.

head = NULL;

head
 Singly Linked List
A linked list in which each node contains only one link
field pointing to the next node in the list

--- 05 60 99

Head Node First data

Node

First node is called the header node where no data

element is stored, but the link field holds the address of
the node containing very first data element.
 Doubly Linked List
•A doubly linked list is a linear data structure in which each
node can have any number of data fields and two link fields
which are used to point to the previous node and the next
node.
--- 05 60 99

Head Node First data

Node
 Circular Linked List
A linked list where the last node points to the header node
is called a circular linked list
There are no NULL linkes.

--- 05 60 99

Head Node First data

Node
 Basic Operations on a list

• Creating a List
• List Traversal
• Inserting an element in a list
• Deleting an element from a list
• Searching a list
• Reversing a list
• Merging two linked lists into a larger list
 Data Structure of Node
struct node
{
int data;
struct node *next;
}; data Next
(Address of
struct node *head; next node)
 Creation of SLL
head=(struct node *)malloc(sizeof(struct node));
head->next=NULL;

//Creation of Link List

Algorithm create(*H)
{ temp=H;
repeat untill choice =‘y’ {
allocate memory to curr;
accept curr->data;
curr->next=NULL;
temp->next=curr;
temp=curr; //temp=temp->next
Read choice;
}
}
 Finding length of Link List
Display Link List
Algorithm display(*H)
Algorithm len(*H)
{
{
if H->next ==NULL
curr=H->next;
Print “ list is empty “
while(curr!=NULL)
else
{
{ print head node values
i++;
curr=H->next;
curr=curr->next;
while(curr!=NULL)
}
{
return(i);
Print curr,curr->data,curr->next;
}
curr=curr->next;
}
}
 Insertion in a linked list
a b
… …
4. 3.
curr
[Link]
nnode Data
[Link] memory for nnode ;[Link] memory
[Link] data for nnode;
[Link]->next = curr->next;
[Link]->next = nnode;

26
Insert a new node by position
Algorithm Insertbypos(*H)
{ i=1 ; curr=H;
allocate memory for nnode node;
read nnode->data and pos; //accept data & position to be
//inserted:
k=len();
if(pos>k+1)
display Data can't be inserted;
else
{
while(curr!=NULL && i<pos)
{
i++;
curr=curr->next;
}
nnode->next=curr->next;
curr->next=nnode;
} //end else
} //end Algorithm
 Deletion from a linked list
a x b
… …
deletedNode
current

Node *deletedNode = current->next;

current->next = current->next->next;
delete deletedNode;
 Delete a node by position
Algorithm delpos(*H)
{
prev=H;ctr=1;
curr=H->next;
read pos; //Accept position of data to be deleted: ;

k=len();
if(k<pos)
display Data can't be deleted;
else
{
while(ctr<pos && curr!=NULL)
{
ctr++;
prev=curr;
curr=curr->next;
}
temp=curr;
prev->next=curr->next;
curr->next=NULL;
free(temp);
}
}
 Reverse of Linked List(Using Pointers)
Algorithm reverse(*H)
{
prev=NULL;
curr=head->next;
while(curr!=NULL)
{
future=curr->next;
curr->next=prev;
prev=curr;
curr=future;
}
head->next=prev;
}
 Sorting of SLL by using pointers
Algorithm sort(*H)
else
{ len=len(H);
{
for i=1 to len-1
prev=curr;
{
curr=curr->next;
prev=H;
}
curr=H->next;
} //end for inner for
for j=0 to <l-i
} //end for outer for
{ temp=curr->next;
} //end Algorithm
if(curr->data > temp->data)
{
prev->next=temp;
curr->next=temp->next;
temp->next=curr;
prev=temp;
}
 Merging of SLL by using pointers
Algorithm merge(*H1,*H2) else
{ {
curr1=H1->next; temp->next=curr2;
curr2=H2->next; temp=curr2;
if(curr1->data<curr2->data) curr2=curr2->next;
{ }
temp=head1; }
flag=1; if(curr1==NULL)
} temp->next=curr2;
else if(curr2==NULL)
{ temp->next=curr1;
temp=head2; if(flag==1)
flag=0; display(head1);
} else
while(curr1!=NULL && curr2!=NULL) display(head2);
{ }
if(curr1->data<curr2->data)
{
temp->next=curr1;
temp=curr1;
curr1=curr1->next;
}
 Arrays Vs Linked Lists
Arrays Linked list

Fixed size: Resizing is expensive Dynamic size

Insertions and Deletions are inefficient: Insertions and Deletions are efficient: No
Elements are usually shifted shifting

Random access i.e., efficient indexing No random access

 Not suitable for operations requiring
accessing elements by index such as sorting

No memory waste if the array is full or almost Since memory is allocated dynamically(acc. to
full; otherwise may result in much memory our need) there is no waste of memory.
waste.

Sequential access is faster [Reason: Elements in Sequential access is slow [Reason: Elements not
contiguous memory locations] in contiguous memory locations]
 Doubly-Linked Lists
 It is a way of going both directions in a linked list, forward and reverse.
 Many applications require a quick access to the predecessor node of
some node in list.
A node in a doubly-linked list store two references:
•A next link; that points to the next node in the list, and
•A prev link; that points to the previous node in the list.
Advantages:
Convenient to traverse the list backwards.
Simplifies insertion and deletion because you no longer have to refer to the
previous node.
Disadvantage:
Increase in space requirements.
prev next

elem node
 Doubly Link List creation
struct node
{
char data[20];
node *next,*prev;

};
Algorithm Create(*H)
{
temp=H;
repeat till choice =y
{
allocate memory for new node
temp->next=curr;
curr->prev=temp;
curr->next=NULL;
temp=curr;
}
Read choice;
}
 Insertion
head current

newNode = new Node(x);

newNode->prev = current; newNode
newNode->next = current->next;
newNode->prev->next = newNode;
newNode->next->prev = newNode;
current = newNode;
 Deletion
head current

oldNode = current;
oldNode->prev->next = oldNode->next;
oldNode->next->prev = oldNode->prev;
delete oldNode;
current = head;
Circular Linked Lists
Allocation of memory for head node using constructor
head=(struct node *)malloc(sizeof(struct node));
head->next=head;

//Creation of Link List

Algorithm create(*H)
{ temp=H;
repeat untill choice =‘y’ {
allocate memory to curr;
accept curr->data;
curr->next=H;
temp->next=curr;
temp=curr; //temp=temp->next
Read choice;
}
}
 Advantages over Singly-linked Lists
• Quick update operations:
such as: insertions, deletions at both ends (head
and tail), and also at the middle of the list.
• A node in a doubly-linked list store two
references:
• A next link; that points to the next node in the list,
and
• A prev link; that points to the previous node in the
list.
 DLLs compared to SLLs
• Advantages: • Disadvantages:
– Can be traversed in either – Requires more space
direction (may be – List manipulations are
essential for some slower (because more
programs) links must be changed)
– Some operations, such as – Greater chance of having
deletion and inserting bugs (because more links
before a node, become must be manipulated)
easier
 • Polynomial
•Array Implementation:
• p1(x) = 8x3 + 3x2 + 2x + 6
• p2(x) = 23x4 + 18x - 3

p1(x) p2(x)

6 2 3 8 -3 18 0 0 23
0 2 0 2 4

Index
represents
exponents
 • Polynomial (continued)

•This is why arrays aren’t good to represent

polynomials:

• p3(x) = 16x21 - 3x5 + 2x + 6

6 2 0 0 -3 0 ………… 0 16

WASTE OF SPACE!
 • Polynomial (continued)

• Advantages of using an Array:

• only good for non-sparse polynomials.

• ease of storage and retrieval.

• Disadvantages of using an Array:

• have to allocate array size ahead of time.

• huge array size required for sparse polynomials.
Waste of space and runtime.
 • Polynomial (continued)

• Linked list Implementation:

• p1(x) = 23x9 + 18x7 + 41x6 + 163x4 + 3

• p2(x) = 4x6 + 10x4 + 12x + 8

P1 23 9 18 7 41 6 163 4 3 0

TAIL (contains pointer)

P2 4 6 10 4 12 1 8 0

NODE (contains coefficient & exponent)

 Revisit Polynomials

coeff exp

[Link] 3 14 2 8 1 0 0

a  3 x14  2 x8  1

[Link] 8 14 -3 10 10 6 **

b  8 x14  3x10  10 x 6
 Node structure of Polynomial
struct polyNode
{// All members in “struct” are public
int coef; // coefficient
int exp; // exponent
struct polyNode *next;
};
 Addition of Two Polynomials (1)
• It is an easy way to represent a polynomial by
a linked list.
• Example of adding two polynomials a and b

[Link] 3 14 2 8 1 0 0

[Link] 8 14 -3 10 10 6 0

q
[Link] 11 14 0 (i) p->exp == q->exp
Addition of Two Polynomials (2)

[Link] 3 14 2 8 1 0 0

[Link] 8 14 -3 10 10 6 0

[Link] 11 14 -3 10 0

(ii) p->exp < q->exp

Addition of Two Polynomials (3)

[Link] 3 14 2 8 1 0 0

[Link] 8 14 -3 10 10 6 0

q
[Link] 11 14 -3 10 2 8 0

(iii) p->exp > q->exp

4-50
 • Polynomial (continued)

• Adding polynomials using a Linked list representation: (storing the result in p3)
To do this, we have to break the process down to cases:

• Case 1: exponent of p1 > exponent of p2

• Copy node of p1 to end of p3.
[go to next node]

• Case 2: exponent of p1 < exponent of p2

• Copy node of p2 to end of p3.
[go to next node]

•Case 3: exponent of p1 = exponent of p2

• Create a new node in p3 with the same exponent and with the sum of the
coefficients of p1 and p2.
 Addition of Polynomial
• Allocate the memory space for head;
• Head->exp=-1

Algorithm add(*H1,*H2)
{
Allocate a memory for H3;
head3->exp=-1;
t3=H3;
t1=H1->next;
t2=H2->next;
while(t1->exp!=-1||t2->exp!=-1)
{
if(t1->exp==t2->exp)
{
Allocate the memory for temp;
Add t1 coeff and t2 coeff in t3 coeff
copy one of the exponent in t3 exp
t3->next=temp;
temp->next=head3;
t3=temp;
Move t1 to next node ;
Move t2 to next node
}
 Addition of Polynomial
else
if exponent of p1 < exponent of p2
Copy node of p2 to end of p3.
else //exponent of p1 > exponent of p2
Copy node of p1 to end of p3

}//end of while

} //end algorithm
 Evaluation of Polynomial
Algorithm eval(*H, x)
{
cur=H->next;
while not end of list
{
using value of x find the sum of terms;
move cur to next node ;
}
print sum;
}
 Generalized Lists
• A generalized list, A, is a finite sequence of n ≥ 0 elements,
a0, a1, a2, …, an-1, where i, is either an atom or a list. The
elements i,0 ≤ i ≤ n – 1, that are not atoms are said to be
the sublists of A.

• A list A is written as A = (a0, …, an-1 ), and the length of

the list is n.

• A list name is represented by a capital letter and an atom is

represented by a lowercase letter.

• a0 is the head of list A and the rest (a1, …, an-1) is the tail
of list A.
 Examples of Generalized Lists
• A = ( ): the null, or empty, list; its length is zero.

• B = (a, (b, c)): a list of length two; its first element is the atom a,
and its second element is the linear list (b, c).

• C = (B, B, ( )): A list of length three whose first two elements

are the list B, and the third element is the null list.

• D = (a, D): is a recursive list of length two; D corresponds to the

infinite list D = (a, (a, (a, …))).

• head(B) = ‘a’ and tail(B) = (b, c), head(tail(C))=B and tail(tail(C))

= ( ).

• Lists may be shared by other lists.

• Lists may be recursive.

• It is a little surprising that every generalized
list can be represented using the node
structure
Tag=0/1 Data Link
• Tag=0 means data
• Tag = 1 means pointer to the sublist
 Representations of Generalized Lists

A=() Empty list

B=(a, (b, c))
B 0 a 1 0

0 b 0 c 0

C 1 1 1 0 0 C=(B, B, ( ))

D 0 a 1 0 D=(a, D)
**
 General Polynomial
p( x, y, z )  x10 y 3 z 2  2 x8 y 3 z 2  3x8 y 2 z 2  x 4 y 4 z  6 x3 y 4 z  2 yz
• P(x, y, z)=
(( x10  2 x8 ) y 3  3x8 y 2 ) z 2  (( x 4  6 x3 ) y 4  2 y) z
• Rewritten as Cz2 + Dz, where C and D are
polynomials.
• Again, in C, it is of the form Ey3 + Fy2, where E and
F are polynomials.
• In general, every polynomial consists of a variable
plus coefficient-exponent pairs. Each coefficient
may be a constant or a polynomial.
• Suppose we need to devise a data representation for them and
consider one typical example, the polynomial P(x,y,z) =

• One can easily think of a sequential representation for P, say

using nodes with four fields: COEF, EXPX, EXPY, and EXPZ.
• But this would mean that polynomials in a different number of
variables would need a different number of fields, adding
another conceptual inelegance to other difficulties.
• These nodes would have to vary in size depending on the
number of variables, causing difficulties in storage
management.
• The idea of using a general list structure with fixed size nodes
arises naturally if we consider re-writing
• P(x,y,z) as
 Linked List-based Stack
Implementation

PUSH pnode
typedef struct
pnode

{ 23 45 67 78 NULL
pnode * next;

int item; TOP

Stack implementation using Linked list includes
} POP
 Inserting Element from top
 Deleting Element from top

DATA STRUCTURE -I UNIT-IV 61