Linked List

April 2, 2007 Programming and Data Structure 1

 Introduction

• A linked list is a data structure which can

change during execution.
– Successive elements are connected by pointers.
– Last element points to NULL.
– It can grow or shrink in size during execution of
a program.
– It can be made just as long as required.
head
– It does not waste memory space.

A B C

April 2, 2007 Programming and Data Structure 2

• Keeping track of a linked list:
– Must know the pointer to the first element of
the list (called start, head, etc.).

• Linked lists provide flexibility in allowing

the items to be rearranged efficiently.
– Insert an element.
– Delete an element.

April 2, 2007 Programming and Data Structure 3

 Illustration: Insertion

A B C

Item to be
X inserted

A B C

April 2, 2007 Programming and Data Structure 4

 Illustration: Deletion
Item to be deleted
A B C

A B C

April 2, 2007 Programming and Data Structure 5

 In essence ...

• For insertion:
– A record is created holding the new item.
– The next pointer of the new record is set to link
it to the item which is to follow it in the list.
– The next pointer of the item which is to precede
it must be modified to point to the new item.
• For deletion:
– The next pointer of the item immediately
preceding the one to be deleted is altered, and
made to point to the item following the deleted
item.
April 2, 2007 Programming and Data Structure 6
 Array versus Linked Lists

• Arrays are suitable for:

– Inserting/deleting an element at the end.
– Randomly accessing any element.
– Searching the list for a particular value.
• Linked lists are suitable for:
– Inserting an element.
– Deleting an element.
– Applications where sequential access is required.
– In situations where the number of elements
cannot be predicted beforehand.

April 2, 2007 Programming and Data Structure 7

 Types of Lists

• Depending on the way in which the links

are used to maintain adjacency, several
different types of linked lists are possible.

– Linear singly-linked list (or simply linear list)

• One we have discussed so far.
head

A B C

April 2, 2007 Programming and Data Structure 8

 – Circular linked list
• The pointer from the last element in the list points
back to the first element.

head

A B C

April 2, 2007 Programming and Data Structure 9

 – Doubly linked list
• Pointers exist between adjacent nodes in both
directions.
• The list can be traversed either forward or backward.
• Usually two pointers are maintained to keep track of
the list, head and tail.
head tail

A B C

April 2, 2007 Programming and Data Structure 10

 Basic Operations on a List

• Creating a list
• Traversing the list
• Inserting an item in the list
• Deleting an item from the list
• Concatenating two lists into one

April 2, 2007 Programming and Data Structure 11

 List is an Abstract Data Type

• What is an abstract data type?

– It is a data type defined by the user.
– Typically more complex than simple data types
like int, float, etc.
• Why abstract?
– Because details of the implementation are
hidden.
– When you do some operation on the list, say
insert an element, you just call a function.
– Details of how the list is implemented or how the
insert function is written is no longer required.
April 2, 2007 Programming and Data Structure 12
 Conceptual Idea

Insert
List
implementation
Delete
and the
related functions
Traverse

April 2, 2007 Programming and Data Structure 13

 Example: Working with linked list
• Consider the structure of a node as
follows:
struct stud {
int roll;
char name[25];
int age;
struct stud *next;
};

/* A user-defined data type called “node” */

typedef struct stud node;
node *head;

April 2, 2007 Programming and Data Structure 14

 Creating a List

April 2, 2007 Programming and Data Structure 15

 How to begin?

• To start with, we have to create a node (the

first node), and make head point to it.
head = (node *) malloc(sizeof(node));

head
roll

name next

age

April 2, 2007 Programming and Data Structure 16

 Contd.

• If there are n number of nodes in the initial

linked list:
– Allocate n records, one by one.
– Read in the fields of the records.
– Modify the links of the records so that the
chain is formed.
head

A B C

April 2, 2007 Programming and Data Structure 17

node *create_list()
{
int k, n;
node *p, *head;
printf ("\n How many elements to enter?");
scanf ("%d", &n);
for (k=0; k<n; k++)
{
if (k == 0) {
head = (node *) malloc(sizeof(node));
p = head;
}
else {
p->next = (node *) malloc(sizeof(node));
p = p->next;
}
scanf ("%d %s %d", &p->roll, p->name, &p->age);
}
p->next = NULL;
return (head);
}
April 2, 2007 Programming and Data Structure 18
• To be called from main() function as:

node *head;
………
head = create_list();

April 2, 2007 Programming and Data Structure 19

 Traversing the List

April 2, 2007 Programming and Data Structure 20

 What is to be done?

• Once the linked list has been constructed

and head points to the first node of the
list,
– Follow the pointers.
– Display the contents of the nodes as they are
traversed.
– Stop when the next pointer points to NULL.

April 2, 2007 Programming and Data Structure 21

void display (node *head)
{
int count = 1;
node *p;

p = head;
while (p != NULL)
{
printf ("\nNode %d: %d %s %d", count,
p->roll, p->name, p->age);
count++;
p = p->next;
}
printf ("\n");
}

April 2, 2007 Programming and Data Structure 22

• To be called from main() function as:

node *head;
………
display (head);

April 2, 2007 Programming and Data Structure 23

 Inserting a Node in a List

April 2, 2007 Programming and Data Structure 24

 How to do?

• The problem is to insert a node before a

specified node.
– Specified means some value is given for the
node (called key).
– In this example, we consider it to be roll.
• Convention followed:
– If the value of roll is given as negative, the
node will be inserted at the end of the list.

April 2, 2007 Programming and Data Structure 25

 Contd.
• When a node is added at the beginning,
– Only one next pointer needs to be modified.
• head is made to point to the new node.
• New node points to the previously first element.
• When a node is added at the end,
– Two next pointers need to be modified.
• Last node now points to the new node.
• New node points to NULL.
• When a node is added in the middle,
– Two next pointers need to be modified.
• Previous node now points to the new node.
• New node points to the next node.

April 2, 2007 Programming and Data Structure 26

void insert (node **head)
{
int k = 0, rno;
node *p, *q, *new;

new = (node *) malloc(sizeof(node));

printf ("\nData to be inserted: ");

scanf ("%d %s %d", &new->roll, new->name, &new->age);
printf ("\nInsert before roll (-ve for end):");
scanf ("%d", &rno);

p = *head;

if (p->roll == rno) /* At the beginning */

{
new->next = p;
*head = new;
}

April 2, 2007 Programming and Data Structure 27

 else
{
while ((p != NULL) && (p->roll != rno))
{
q = p;
p = p->next;
}
The pointers
if (p == NULL) /* At the end */ q and p
{ always point
q->next = new; to consecutive
new->next = NULL; nodes.
}
else if (p->roll == rno)
/* In the middle */
{
q->next = new;
new->next = p;
}
}
}
April 2, 2007 Programming and Data Structure 28
• To be called from main() function as:

node *head;
………
insert (&head);

April 2, 2007 Programming and Data Structure 29

 Deleting a node from the list

April 2, 2007 Programming and Data Structure 30

 What is to be done?

• Here also we are required to delete a

specified node.
– Say, the node whose roll field is given.
• Here also three conditions arise:
– Deleting the first node.
– Deleting the last node.
– Deleting an intermediate node.

April 2, 2007 Programming and Data Structure 31

 void delete (node **head)
{
int rno;
node *p, *q;

printf ("\nDelete for roll :");

scanf ("%d", &rno);

p = *head;
if (p->roll == rno)
/* Delete the first element */
{
*head = p->next;
free (p);
}

April 2, 2007 Programming and Data Structure 32

 else
{
while ((p != NULL) && (p->roll != rno))
{
q = p;
p = p->next;
}

if (p == NULL) /* Element not found */

printf ("\nNo match :: deletion failed");

else if (p->roll == rno)

/* Delete any other element */
{
q->next = p->next;
free (p);
}
}
}

April 2, 2007 Programming and Data Structure 33

 Few Exercises to Try Out
• Write a function to:
– Concatenate two given list into one big list.
node *concatenate (node *head1, node *head2);
– Insert an element in a linked list in sorted order.
The function will be called for every element to be
inserted.
void insert_sorted (node **head, node *element);
– Always insert elements at one end, and delete
elements from the other end (first-in first-out
QUEUE).
void insert_q (node **head, node*element)
node *delete_q (node **head) /* Return the deleted node */

April 2, 2007 Programming and Data Structure 34

 Abstract Data Types

April 2, 2007 Programming and Data Structure 35

 Definition

• An abstract data type (ADT) is a specification

of a set of data and the set of operations that
can be performed on the data.
• Such data type is abstract in the sense that it
is independent of various concrete
implementations.
• Some examples follow.

April 2, 2007 Programming and Data Structure 36

 Example 1 :: Complex numbers
struct cplx {
float re;
Structure
float im;
}
definition
typedef struct cplx complex;

complex *add (complex a, complex b);

complex *sub (complex a, complex b);
complex *mul (complex a, complex b); Function
complex *div (complex a, complex b);
prototypes
complex *read();
void print (complex a);

April 2, 2007 Programming and Data Structure 37

 add

sub

mul Complex
Number
div

read

print
April 2, 2007 Programming and Data Structure 38
 Example 2 :: Set manipulation
struct node {
int element;
Structure
struct node *next;
}
definition
typedef struct node set;

set *union (set a, set b);

set *intersect (set a, set b);
set *minus (set a, set b); Function
void insert (set a, int x); prototypes
void delete (set a, int x);
int size (set a);

April 2, 2007 Programming and Data Structure 39

 union

intersect

minus
Set
insert

delete

size
April 2, 2007 Programming and Data Structure 40
 Example 3 :: Last-In-First-Out STACK

Assume:: stack contains integer elements

void push (stack s, int element);

/* Insert an element in the stack */
int pop (stack s);
/* Remove and return the top element */
void create (stack s);
/* Create a new stack */
int isempty (stack s);
/* Check if stack is empty */
int isfull (stack s);
/* Check if stack is full */

April 2, 2007 Programming and Data Structure 41

 push

pop

create
STACK
isempty

isfull

April 2, 2007 Programming and Data Structure 42

 Visualization of a Stack

In Out

C B A B C

April 2, 2007 Programming and Data Structure 43

 Contd.

• We shall look into two different ways of

implementing stack:
– Using arrays
– Using linked list

April 2, 2007 Programming and Data Structure 44

 Example 4 :: First-In-First-Out QUEUE

Assume:: queue contains integer elements

void enqueue (queue q, int element);

/* Insert an element in the queue */
int dequeue (queue q);
/* Remove an element from the queue */
queue *create();
/* Create a new queue */
int isempty (queue q);
/* Check if queue is empty */
int size (queue q);
/* Return the no. of elements in queue */

April 2, 2007 Programming and Data Structure 45

 enqueue

dequeue

create
QUEUE
isempty

size

April 2, 2007 Programming and Data Structure 46

 Visualization of a Queue

Out
In

B A
C B A

April 2, 2007 Programming and Data Structure 47

 Stack Implementation
a) Using arrays
b) Using linked list

April 2, 2007 Programming and Data Structure 48

 Basic Idea

• In the array implementation, we would:

– Declare an array of fixed size (which determines the
maximum size of the stack).
– Keep a variable which always points to the “top” of the
stack.
• Contains the array index of the “top” element.
• In the linked list implementation, we would:
– Maintain the stack as a linked list.
– A pointer variable top points to the start of the list.
– The first element of the linked list is considered as the
stack top.

April 2, 2007 Programming and Data Structure 49

 Declaration
#define MAXSIZE 100 struct lifo
{
struct lifo int value;
{ struct lifo *next;
int st[MAXSIZE]; };
int top; typedef struct lifo
}; stack;
typedef struct lifo
stack; stack *top;

ARRAY LINKED LIST

April 2, 2007 Programming and Data Structure 50

 Stack Creation
void create (stack *s) void create (stack **top)
{ {
(*s).top = -1; *top = NULL;

/* [Link] points to /* top points to NULL,

last element indicating empty
pushed in; stack */
initially -1 */ }
}
LINKED LIST
ARRAY

April 2, 2007 Programming and Data Structure 51

 Pushing an element into the stack
void push (stack *s, int element)
{
if ((*s).top == (MAXSIZE-1))
{
printf (“\n Stack overflow”);
exit(-1);
}
else
{
(*s).top ++;
(*s).st [(*s).top] = element;
}
}

ARRAY
April 2, 2007 Programming and Data Structure 52
 void push (stack **top, int element)
{
stack *new;
new = (stack *) malloc(sizeof(stack));
if (new == NULL)
{
printf (“\n Stack is full”);
exit(-1);
}
new->value = element;
new->next = *top;
*top = new;
}

LINKED LIST
April 2, 2007 Programming and Data Structure 53
 Popping an element from the stack

int pop (stack *s)

{
if ((*s).top == -1)
{
printf (“\n Stack underflow”);
exit(-1);
}
else
{
return ((*s).st[(*s).top--]);
}
}

ARRAY
April 2, 2007 Programming and Data Structure 54
 int pop (stack **top)
{
int t;
stack *p;
if (*top == NULL)
{
printf (“\n Stack is empty”);
exit(-1); LINKED LIST
}
else
{
t = (*top)->value;
p = *top;
*top = (*top)->next;
free (p);
return t;
}
}
April 2, 2007 Programming and Data Structure 55
 Checking for stack empty
int isempty (stack s) int isempty (stack *top)
{ {
if ([Link] == -1) if (top == NULL)
return 1; return (1);
else else
return (0); return (0);
} }

ARRAY LINKED LIST

April 2, 2007 Programming and Data Structure 56

 Checking for stack full

int isfull (stack s) • Not required for linked list

{ implementation.
if ([Link] == • In the push() function, we
(MAXSIZE–1)) can check the return value
return 1; of malloc().
else – If -1, then memory cannot
return (0); be allocated.
}

ARRAY LINKED LIST

April 2, 2007 Programming and Data Structure 57

 Example main function :: array
#include <stdio.h> push(&A,30);
#define MAXSIZE 100 push(&B,100); push(&B,5);
struct lifo printf (“%d %d”, pop(&A),
{ pop(&B));
int st[MAXSIZE];
int top; push (&A, pop(&B));
}; if (isempty(B))
typedef struct lifo stack; printf (“\n B is empty”);
main() }
{
stack A, B;
create(&A); create(&B);
push(&A,10);
push(&A,20);

April 2, 2007 Programming and Data Structure 58

 Example main function :: linked list
#include <stdio.h> push(&A,30);
struct lifo push(&B,100);
{ push(&B,5);
int value;
printf (“%d %d”,
struct lifo *next;
pop(&A), pop(&B));
};
typedef struct lifo stack; push (&A, pop(&B));

main() if (isempty(B))
{ printf (“\n B is
stack *A, *B; empty”);
create(&A); create(&B); }
push(&A,10);
push(&A,20);

April 2, 2007 Programming and Data Structure 59

 Queue Implementation using Linked
List

April 2, 2007 Programming and Data Structure 60

 Basic Idea

• Basic idea:
– Create a linked list to which items would be
added to one end and deleted from the other
end.
– Two pointers will be maintained:
• One pointing to the beginning of the list (point from
where elements will be deleted).
Rear
• Another pointing to the end of the list (point where
new elements will be inserted).

Front
April 2, 2007 Programming and Data Structure 61
 Declaration

struct fifo {
int value;
struct fifo *next;
};
typedef struct fifo queue;

queue *front, *rear;

April 2, 2007 Programming and Data Structure 62

 Creating a queue

void createq (queue **front, queue **rear)

{
*front = NULL;
*rear = NULL;
}

April 2, 2007 Programming and Data Structure 63

 Inserting an element in queue
void enqueue (queue **front, queue **rear, int x)
{
queue *ptr;
ptr = (queue *) malloc(sizeof(queue));

if (*rear == NULL) /* Queue is empty */

{
*front = ptr;
*rear = ptr;
ptr->value = x;
ptr->next = NULL;
}
else /* Queue is not empty */
{
(*rear)->next = ptr;
*rear = ptr;
ptr->value = x;
ptr->next = NULL;
}
}

April 2, 2007 Programming and Data Structure 64

 Deleting an element from queue
int dequeue (queue **front, queue **rear)
{
queue *old; int k;

if (*front == NULL) /* Queue is empty */

printf (“\n Queue is empty”);
else if (*front == *rear) /* Single element */
{
k = (*front)->value;
free (*front); front = rear = NULL;
return (k);
}
else
{
k = (*front)->value; old = *front;
*front = (*front)->next;
free (old);
return (k);
}
}

April 2, 2007 Programming and Data Structure 65

 Checking if empty

int isempty (queue *front)

{
if (front == NULL)
return (1);
else
return (0);
}

April 2, 2007 Programming and Data Structure 66

 Example main function
#include <stdio.h> enqueue(&Af,&Ar,30);
struct fifo
printf (“%d %d”,
{
dequeue (&Af,&Ar),
int value;
dequeue(&Af,&Ar));
struct fifo *next;
}; if (isempty(Af))
typedef struct fifo queue; printf (“\n Q is empty”);
}
main()
{
queue *Af, *Ar;
create (&Af, &Ar);
enqueue (&Af,&Ar,10);
enqueue (&Af,&Ar,20);

April 2, 2007 Programming and Data Structure 67

 Some Applications of Stack

April 2, 2007 Programming and Data Structure 68

 Applications ….

• Handling function calls and return

• Handling recursion
• Parenthesis matching
• Evaluation of expressions
– Polish postfix and prefix notations

April 2, 2007 Programming and Data Structure 69