List ADT

B.Bhuvaneswaran
Assistant Professor (SS)
Department of Computer Science & Engineering
Rajalakshmi Engineering College
Thandalam
Chennai 602 105
[email protected]

Abstract data type

In programming each program is
breakdown into modules, so that no
routine should ever exceed a page.
Each module is a logical unit and does a
specific job modules which in turn will call
another module.

Advantages

Modularity has several advantages

Modules can be compiled separately which

makes debugging process easier.
Several modules can be implemented and
executed simultaneously.
Modules can be easily enhanced.

Advantages
Abstract Data type is an extension of
modular design.
An abstract data type is a set of
operations such as Union, Intersection,
Complement, Find etc.,
The basic idea of implementing ADT is that
the operations are written once in
program and can be called by any part of
the program.

The List ADT

List is an ordered set of elements.
The general form of the list is

A1, A2, A3, . . . , AN

A1 - First element of the list

AN - Last element of the list
N - Size of the list
If the element at position i is Ai then its
successor is Ai+1, and its predecessor is
Ai-1.

Operations performed on List

Insert (X, 5) - Insert the element X after
the position 5.
Delete (X) - The element X is deleted.
Find (X) - Returns the position of X.
Next (i) - Returns the position of its
successor element i+1.
Previous (i) - Returns the position of its
predecessor i-1 .
PrintList - Contents of the list is displayed.
MakeEmpty - Makes the list empty.

Implementation of List ADT

Array Implementation
Linked List Implementation
Cursor Implementation

Array implementation of List

Array is a collection of specific number of

data stored in a consecutive memory
locations.

Insertion and Deletion operation are expensive

as it requires more data movement
Find and PrintList operations takes constant
time.
Even if the array is dynamically allocated, an
estimate of the maximum size of the list is
required which considerably wastes the
memory space.

Array implementation of List

Linked List implementation

Linked list consists of series of nodes.
Each node contains the element and a
pointer to its successor node.
The pointer of the last node points to
NULL.
Insertion and deletion operations are
easily performed using linked list.

Types of Linked List

Singly Linked List
Doubly Linked List
Circular Linked List

Singly Linked List

A singly linked list is a linked list in which

each node contains only one link field
pointing to the next node in the list.

Linked List with a header

Declaration for Linked List

struct node ;
typedef struct Node *List ;
typedef struct Node *Position ;
int IsLast (List L) ;
int IsEmpty (List L) ;
Position Find (int X, List L) ;
void Delete (int X, List L) ;
Position FindPrevious (int X, List L) ;
Position FindNext (int X, List L) ;
void Insert (int X, List L, Position P) ;
void Deletelist(List L) ;
struct Node
{
int element ;
Position Next ;
};

Routine to insert an element in the list

void Insert (int X, List L, Position P)
// Insert after the position P
{
Position Newnode;
Newnode = malloc (sizeof (Struct Node));
if (Newnode != NULL)
{
Newnode->Element = X;
Newnode->Next = P->Next;
P->Next = Newnode;
}
}

Check whether the list is empty

// Returns 1 if L is empty
int IsEmpty (List L)
{
if(L->Next == NULL)
return (1);
}

Check whether the current pos is last

// Returns 1 if P is the last position in L
int IsLast (Position R, List L)
{
if (P->Next == NULL)
return (1);
}

Find routine
Position Find (int X, List L)
{
// Returns the position of X in L
// NULL if X is not found
Position P;
P = L->Next;
while (P != NULL && P->Element != X)
P = P->Next;
return P;
}

FindPrevious routine
position FindPrevious (int X, List L)
{
// Returns the position of the predecessor
Position P;
P = L;
while(P->Next!=NULL && P->Next->Element!=X)
P = P->Next;
return P;
)

FindNext routine
position FindNext (int X, List L)
{
// Returns the position of its successor
P = L->Next;
while(P->Next!=NULL && P->Element!=X)
P = P->Next;
return P->Next;
}

Delete an element from the List

void Delete (int X, List L)
{
// Delete the first occurrence of X from the List
Position P, Temp;
P = FindPrevious (X,L);
if (!IsLast(P,L))
{
Temp = P->Next;
P->Next = Temp->Next;
Free (Temp);
}
}

Routine to delete the List

void DeleteList (List L)
{
Position P, Temp:
P = L->Next;
L->Next = NULL;
while (P != NULL)
{
Temp = P->Next
free (P);
P = Temp;
}
}

Doubly Linked List

A Doubly linked list is a linked list in which
each node has three fields namely data
field, forward link (FLINK) and Backward
Link (BLINK).
FLINK points to the successor node in the
list whereas BLINK points to the
predecessor node.

Node in doubly linked list

Doubly linked list

Structure declaration
struct Node
{
int Element;
struct Node *FLINK;
struct Node *BLINK
};

Insert an element in a DLL

void Insert (int X, List L, Position P)
{
struct Node *Newnode;
Newnode = malloc (size of (struct Node));
if (Newnode != NULL)
{
Newnode->Element = X;
Newnode->Flink = P->Flink;
P->Flink->Blink = Newnode:
P->Flink = Newnode ;
Newnode->Blink = P;
}
}

Routine to delete an element

void Delete (int X, List L)
{
Position P;
P = Find (X, L);
if ( IsLast (P, L))
{
Temp = P:
P->Blink->Flink = NULL;
free (Temp);
}
else
{
Temp = P;
P->Blink->Flink = P->Flink;
P->Flink->Blink = P->Blink;
free (Temp);
}
}

Advantage
Deletion operation is easier.
Finding the predecessor & Successor of a
node is easier.

Disadvantage

More Memory Space is required since it

has two pointers.

Circular Linked List

In circular linked list the pointer of the last
node points to the first node.
Circular linked list can be implemented as
Singly linked list and Doubly linked list
with or without headers.

Singly Linked Circular List

A singly linked circular list is a linked list

in which the last node of the list points to
the first node.

Doubly Linked Circular List

A doubly linked circular list is a Doubly

linked list in which the forward link of the
last node points to the first node and
backward link of the first node points to
the last node of the list.

Advantages of Circular Linked List

It allows to traverse the list starting at any
point.
It allows quick access to the first and last
records
Circularly doubly linked list allows to
traverse the list in either direction.

Applications of Linked List

Polynomial ADT
Radix Sort
Multilist

Polynomial ADT

We can perform the polynomial

manipulations such as addition,
subtraction and differentiation etc.

Dec. for LL imp. of Polynomial ADT

struct poly
{
int coeff ;
int power;
struct poly *Next;
}*list1, *list2, *list3;

Creation of the polynomial

poly create (poly *head1, poly *newnode1)
{
poly *ptr;
if (head1 == NULL)
{
head1 = newnode1;
return (head1);
}
else
{
ptr = head1;
while (ptr->next != NULL)
ptr = ptr->next;
ptr->next = newnode1;
}
return (head1);
}

Addition of two polynomials

void add ()
{
poly *ptr1, *ptr2, *newnode;
ptr1 = list1;
ptr2 = list2;
while (ptr1 != NULL && ptr2 != NULL)
{
newnode = malloc (sizeof (struct poly));
if (ptr1->power == ptr2->power)
{
newnode->coeff = ptr1->coeff + ptr2->coeff;
newnode->power = ptr1->power;
newnode->next = NULL;
list3 = create (list3, newnode);
ptr1 = ptr1->next;
ptr2= ptr2->next;
}

else
{

if (ptr1->power > ptr2->power)

{
newnode->coeff = ptr1->coeff;
newnode->power = ptr1->power;
newnode->next = NULL;
list3 = create (list3, newnode);
ptr1 = ptr1->next;
}
else
{
newnode->coeff = ptr2->coeff;
newnode->power = ptr2->power;
newnode->next = NULL;
list3 = create (list3, newnode);
ptr2= ptr2->next;
}

Subtraction of two polynomial

void sub ()
{
poly *ptr1, *ptr2, *newnode;
ptr1 = list1;
ptr2 = list2;
while (ptr1 != NULL && ptr2 != NULL)
{
newnode = malloc (sizeof (struct poly));
if (ptr1->power == ptr2->power)
{
newnode->coeff = ptr1->coeff - ptr2->coeff;
newnode->power = ptr1->power;
newnode->next = NULL;
list3 = create (list3, newnode);
ptr1 = ptr1->next;
ptr2= ptr2->next;
}

else
{

if (ptr1->power > ptr2->power)

{
newnode->coeff = ptr1->coeff;
newnode->power = ptr1->power;
newnode->next = NULL;
list3 = create (list3, newnode);
ptr1 = ptr1->next;
}
else
{
newnode->coeff = -(ptr2->coeff);
newnode->power = ptr2->power;
newnode->next = NULL;
list3 = create (list3, newnode);
ptr2= ptr2->next;
}

Polynomial differentiation
void diff ( )
{
poly *ptr1, *newnode;
ptr1 = list1;
while (ptr1 != NULL)
{
newnode = malloc (sizeof (struct poly));
newnode->coeff = ptr1->coeff*ptr1->power;
newnode->power = ptr1->power - 1 ;
newnode->next = NULL;
list3 = create (list3, newnode);
ptr1 = ptr1->next;
}
}

Radix sort (Or) Card sort

Radix Sort is the generalised form of Bucket sort.

It can be performed using buckets from 0 to 9.
In First Pass, all the elements are sorted
according to the least significant bit.
In second pass, the numbers are arranged
according to the next least significant bit and so
on this process is repeated until it reaches the
most significant bits of all numbers.
The numbers of passes in a Radix Sort depends
upon the number of digits in the numbers given.

Pass 1

Input : 25, 256, 80, 10, 8, 15, 174, 187

Pass 2

Input : 80, 10, 174, 25, 15, 256, 187, 8

Pass 3

Input: 8, 10, 15, 25, 256, 174, 80, 187

Maximum number of digits in the given list

is 3.
Therefore the number of passes required
to sort the list of elements is 3.

Multi Lists
More complicated application of linked list
is multilist.
It is useful to maintain student
registration, employee involved in
different projects etc.,
Multilist saves space but takes more time
to implement.

Multilist imp. for emp. Project Alloc.

An employee can involve in any number of

projects and each project can be implemented by
any number of employees.
Employee E1 is working on project P1, E2 is
working on project P2 & E3 is working on project
P1.
Project P1 is implemented by the Employees E1 &
E3.
Project P2 is implemented by the Employee E2,

Cursor Implementation of Linked Lists

Cursor implementation is very useful

where linked list concept has to be
implemented without using pointers.

Pointer Vs Cursor imp. of LL

Pointer Implementation

Cursor Implementation

Data are stored in a collection of

structures.
Each structure contains a data and
next
pointer.

Data are stored in a global aray of

structures. Here array index is
considered as an address.

Malloc function is used to create a

node and
freefunction is used to released the
cell.

It maintains a list of free cells called

cursors space in which slot 0 is
considered as a header and Next is
equivalent to the pointer which points
to the next slot.

Initialized cursorspace

Declaration
typedef int ptrtoNode;
typedef ptrtoNode position;
void Initialize cursorspace (void);
int IsEmpty (List L);
int IsLast (position P, List L);
position Find (int X, List L);
void Delete (int X, List L);
void Insert (int X, List L, position P);
struct Node
{
int Element;
position Next;
};
struct Node Cursorspace [space size];

Routine for cursor alloc. & cursor free

static position CursorAlloc (void)
{
position P;
P = CursorSpace [0].Next;
CursorSpace [0].Next = CursorSpace [P].Next;
return P;
}
Static void CursorFree (position P)
{
CursorSpace [P].Next = CursorSpace [0].Next;
CursorSpace [0].Next = P;
}

Check whether the list is empty

int IsEmpty (List L)
{
// Returns 1 if the list is Empty
if (CursorSpace[0].Next == 0)
return (1);
}

Routine for IsLast

int IsLast (Position P, List L)
{
// Returns 1 if the P is in last position
if (CursorSpace[P].Next == 0)
return (1);
}

Routine to Find an element

position Find (int X, List L)
{
position P;
P = CursorSpace[L].Next;
while (P && CursorSpace[P].Element != X)
P = CursorSpace [P].Next;
return P;
}

Routine to delete an element

void Delete (int X, List L)
{
position P, temp;
P = FindPrevious (X, L);
if (!IsLast (P, L))
{
temp = CursorSpace[P].Next;
CursorSpace[P].Next = CursorSpace[temp].Next;
CursorFree (temp);
}
}

Routine for insertion

void Insert (int X, List L, position P)
{
position newnode;
newnode = CursorAlloc ( );
if (newnode != 0)
CursorSpace[newnode].Element = X;
CursorSpace[newnode].Next = CursorSpace[P].Next;
CursorSpace[P].Next = newnode;
}

Ex. of a Cursor Implementation of LL

The List X has A, B and list Y has C, D.

References
Mark Allen Weiss, Data Structures and
Algorithm Analysis in C++, 3rd Edition,
Pearson Education, 2006.
P.Revathy, Dr.S.Poonkuzhali, Data
Structures and Algorithms, 1st Edition,
Charulatha Publications, 2009.