C-programming-class 12

Session 12

Linked List

1

Session Objectives • To study the concepts of linked list. • To study the different operations performed on the linked list.

2

Session Topics • Introduction to linked list. • Singly linked list. • Circular linked list.

3

Linked Lists A linked list is a data structure which is a collection of zero or more nodes where each node has some information. Between, each node in the list, there exists a logical relationship so that given the address of the first node, any node in that list can be obtained. Each node can hold the data along with a pointer field using which address of the next node can be obtained. 4

Types of Linked Lists: Singly linked lists Circularly singly linked lists Doubly linked lists Circular doubly linked lists

5

Storage representation of a node In a linked allocation technique, a node in a linked list has two fields. infowhich contains the actual information linkwhich contains address of the next node A node can be represented as a structure as follows struct node { int info; struct node *link; }; 6

Singly linked list A singly linked list is a linked list, where each node has designated field called link field which contains address of the next node. If there exists only one link field in each and every node In the list, then the list is a Singly Linked List. info

link

5

1020

node first = 1004

info

link

info

15

1012

25

link

1012

1020

Memory representation of singly linked list first

info

link

5 node 1004

info

link

15

info

link

25 1020

1012

Pictorial Representation of Singly linked list

7

Operations performed on singly linked list • Inserting a node into the list • Deleting a node from the list • Display the contents of the list 10 temp

20

30

40

first

To insert an item at the front end 10 first

20

30

40

After inserting 10 8

Function to insert an item at the front end of the list NODE insert_front(int item,NODE first) { NODE temp; temp = get_node(); /* Obtain a node */ temp->info = item; /* Insert the item */ temp->link = first; return temp; /* Return the first node */ }

9

Function to obtain a new node from the availability list NODE get_node() { NODE x; /* Try to allocate the required size of memory */ x = (NODE)malloc(sizeof(struct node)); if(x == NULL) { printf(“Out of memory\n”);/*Allocation failed*/ exit(0); } /* Allocation successful, return address */ return x; } 10

To delete a node from the front end first

10

20

30

40

10

20

30

40

temp

first

temp

first

20

30

40

11

Function to delete an item from the front end of the list NODE delete_front(NODE first) { NODE temp; if(first == NULL) /* Is list empty */ { printf(“List empty\n”); return first; } /* Retain the address of the node to be deleted*/ temp = first; first = first->link; /* Update first */ /* Display and delete the front node */ printf(“The item deleted is %d\n”,temp->info); free_node(temp); return first; /* return address of first node */ } 12

To insert an item at the rear end cur

10

20

30

first first

temp

cur

10

20

30

40

10

20

30

40

13

Function to insert an item at the rear end of the list NODE insert_rear(int item, NODE first) { NODE temp; /* Node to be inserted */ NODE cur; /* To hold the address of the last node*/ temp = get_node(); temp ->info = item; temp->link = NULL; /* Return the new node created if list is empty*/ if(first==NULL) return temp; /* If list exists,obtain address of last node */ cur = first; while(cur->link != NULL) { cur = cur->link; } /* Insert the node at the end */ cur->link = temp; /* Return address of the first node */ return first; }

14

Delete a node from the rear end first

10

After deleting first = NULL

prev first

10

20

30

cur

40

prev first

10

20

30

40

15

Function to delete an item from the rear end of the list NODE delete_rear(NODE first) { NODE cur,prev; if(first == NULL) { printf(“List empty!Cannot delete\n”); return first; } if(first ->link == NULL) { /* Only one node is present and delete it*/ printf(“The item to be deleted is %d\n”,first->info); freenode(first); /*Return to availability list */ first = NULL; return first; }

16

contd….Function to delete an item from the rear end of the list /* Obtain address of the last node and just previous to that */ prev = NULL; cur = first; while(cur->link!=NULL) { prev = cur; cur = cur->link; } printf(“The item deleted is %d\n”,cur->info); freenode(cur); /* Delete the last node */ prev->link = NULL; /* Node pointed to by prev is made the last node*/ return first; /* Return address of the first node */ } 17

Circular singly linked list Linear linked list containing the address of the first node in the link field of the last node results in a Circular Singly linked list or Circular list. last

Pictorial representation of Circular singly linked list

NOTE: In a circular list if the address of any node x is known, one can traverse the entire list from that node and thus, all nodes are reachable. Operations performed on a Circular list: insert _front , insert_rear, delete_front, delete_rear

18

To insert a node at the front end of a Circular list last

30

20

40

10 last

20

30

40

19

Function to insert an item at the front end of the Circular list NODE insert_front(int item, NODE last) { NODE temp; temp=get_node();/*Create a new node to be inserted*/ temp->info = item; if(last == NULL)/* Make temp as the first node */ last = temp; else /*Insert at the front end */ temp->link = last->link; last->link = temp; /*Link last node to first node*/ return last; /* Return the last node */ }

20

Insert a node at the rear end last

10

20

30

last

10

20

30

temp

40

21

Function to insert an item at the rear end of the list NODE insert_rear(int item,NODE last) { NODE temp; temp = get_node; /*Create a new node */ temp->info = item; if(last == NULL)/*Make temp as the first node*/ last = temp; else /*Insert at the rear end*/ temp->link = last->link; last->link = temp; /*Link last node to first node*/ return temp;/*Make the new node as the last node */ } 22

Delete a node from the front end first

last

10

20

30

40

To delete an item from the front end

20

30

40

After deleting the first item 23

Function to delete an item from the front end of the list NODE delete_front(NODE last) { NODE temp,first; if(last == NULL) /* If no list exists */ { printf(“List is empty\n”); return NULL; } if(last->link ==last) /* Is there only one node? */ { printf(“The item deleted is %d\n”,last->info); free_node(last); return NULL; } first=last->link; /*Obtain the item to be deleted*/ /*Store new first node in link of last*/ last->link = first->link; printf(“The item deleted is %d\n”,first->info); free_node(first); /*Delete the old first node */ return last; }

24

Function to delete a node from the rear end 10

20

30

40

To delete a node from the rear end

10

20

30

After deleting a node from the rear end

25

Function to delete a node from the rear end NODE delete_rear(NODE last){ NODE prev; if(last == NULL) /* If no list exists */ { printf(“List is empty\n”); return NULL; } if(last->link ==last) /* Is there only one node? */ { printf(“The item deleted is %d\n”,last->info); free_node(last); return NULL; } prev = last->link; /*Obtain address of previous node*/ while(prev->link != last) prev = prev->link; prev->link = last->link;/*prev node is made the last node*/ printf(“The item deleted is %d\n”,last->info); free_node(last);/*Delete the old node*/ return prev; /* return the new last node */

}

26

Summary • A singly linked list is a linked list, where each node has designated field called link field which contains address of the next node. • If there exists only one link field in each and every node In the list, then the list is a Singly Linked List. • Linear linked list containing the address of the first node in the link field of the last node results in a Circular Singly linked list or Circular list. • In a circular list if the address of any node x is known, one can traverse the entire list from that node and thus, all nodes are reachable. 27

Thank You!

28