Singly & Circular Linked list

Easy way to learn linked list

1. Singly & Circular Linked List Presented by Md. Zabirul Islam Md. Sharzul Mostafa Manon Rahman Aparajita Dola and Shahriar Parvej Department of CSE, KUET

2. Outlines Introduction Advantage of a Link List over Array Link List Declaration Basic Link List Operation Circular Link List Application Disadvantage Computer Science & Engineering , KUET 01/43

3. Introduction What Is Linked List? The most commonly used data structure to store data in memory. A linear collection of data elements, called nodes. Unlike arrays, linked list elements are not stored at adjacent location. The nodes connect by pointers . Computer Science & Engineering , KUET 02/43

4. What’s wrong with Array and Why linked lists? Insertions and deletions are simple and faster. Linked list is able to grow in size . Linked List reduces the access time. No wastage of memory. Computer Science & Engineering , KUET 03/43 Disadvantages of arrays as storage data structures: Linked lists solve some of these problems : Insertion and deletion operations are slow. Slow searching in unordered array. Wastage of memory. Fixed size.

5. Singly Linked List Singly linked list is a collection of nodes. Each node contains two parts. The data contains elements . Link contains address of next node . data link Computer Science & Engineering , KUET 04/43 Node

6. Structure of singly linked list link data A B C link link data data head The head always points to the first node . All nodes are connected to each other through Link fields. Null pointer indicated end of the list. Computer Science & Engineering , KUET 05/43 X

7. Circular linked list A circular linked list is one which has No ending. The null pointer in the last node of a linked list is replaced with the address of its first node . Computer Science & Engineering , KUET 06/43

8. Structure of circular linked list CIRCULAR LINKED LIST:- 4000 1000 2000 B 2000 C 4000 A 1000 Computer Science & Engineering , KUET 07/43

9. Operations on linked list The basic operations on linked lists are : Creation Insertion Deletion Traversing Searching Computer Science & Engineering , KUET 08/43

10. The creation operation is used to create a linked list. Declare Node struct for nodes. Data - any type Link - a pointer to the next node. Struct node{ int data; Struct node *link; } Computer Science & Engineering , KUET 09/43 What Is creation

11. Allocate a new node Insert new element Make new node point to null C reate head to point to new node Algorithm create a new node new->data=item new-> link=NULL head=new What Is creation Computer Science & Engineering , KUET 10/43

12. Creation new->data=item new->link=NULL head=new Computer Science & Engineering , KUET 11/43 X head New Node A

13. What I s Insertion Insertion operation is used to insert a new node in the linked list at the specified position. W hen the list itself is empty , the new node is inserted as a first node. Computer Science & Engineering , KUET 12/43

14. Types of Insertion There are many ways to insert a new node into a list : As the new first element. As the new last element. Before a given value. After a given value. Computer Science & Engineering , KUET 13/43

15. Inserting at the beginng Allocate a new node Insert new element Make new node to point to old head Update head to point to new node Algorithm create a new node new->data=item new->link=head head=new Computer Science & Engineering , KUET 14/43

16. Inserting at the beginning X link link data data head New Node B C A Computer Science & Engineering , KUET 15/43 new->link=head head=new

17. Inserting at the last Allocate a new node Insert new element Searching the last node Have old last node point to new node Update new node that point to null create a new node new->data=item ptr=head while(ptr- >link!=null) ptr=ptr>link ptr->link=new new->link=NULL Computer Science & Engineering , KUET 16/43 Algorithm

18. Inserting at the last B C link link data data A X New Node Computer Science & Engineering , KUET 17/43 head ptr ->link=new new->link=NULL

19. Inserting before given a value Allocate a new node Insert new element Searching the given node Store the previous node Update new to point to previous node link Update previous node to point to new node create a new node new->data=item ptr=head while(ptr->info!=data ) temp=ptr ptr = ptr>link new- > link=temp-> link temp-> link=new Computer Science & Engineering , KUET 18/43 Algorithm

20. Inserting before given a value link data A X B link link data data head New Node D Computer Science & Engineering , KUET 19/43 C temp ptr new->link=temp->link temp->link=new

21. Inserting after given a value Allocate a new node, new Insert new element Searching the node Update new to point to the link of the given node Update given node to point to new node create a new node new->data=item ptr=head while(ptr- >info!=data) ptr=ptr>link new->link=ptr->link p tr->link=new Algorithm Computer Science & Engineering , KUET 20/43 Algorithm

22. Inserting after given a value link data A X B link link data data New Node D Computer Science & Engineering , KUET 21/43 C ptr head new->link= ptr ->link ptr ->link=new

23. What I s Deletion? Deletion operation is used to delete a particular node in the linked list. we simply have to perform operation on the link of the nodes(which contains the address of the next node) to delete a particular element. Computer Science & Engineering , KUET 22/43

24. Types of Deletion Deletion operation may be performed in the following conditions: D elete first element. Delete last element. Delete before a given value. Delete after a given value. Delete a particular element Computer Science & Engineering , KUET 23/43

25. Deleting the first node Declare a node Assign head to the new node Update head with the link of the new node Algorithm srt =head head= srt ->link Computer Science & Engineering , KUET 24/43

26. Deleting the first node X link link data data head d ata link B C A Computer Science & Engineering , KUET 25/43 srt =head head= srt ->link srt

27. Deleting the last node Declare nodes srt , temp Traverse the list and u pdate temp with the value of srt If the link of srt is NULL, update the link of temp with NULL and break the loop Algorithm declare srt , temp for( srt =head;;temp= srt , srt = srt ->link) if( srt ->link==NULL) temp->link=NULL; Exit; Computer Science & Engineering , KUET 26/43

28. Deleting the last node X link link data data head d ata link B C A Computer Science & Engineering , KUET 27/43 X

29. Deleting after a given value Declare a node srt Search the element to delete after Update link of the node with the link of the next node Node * srt srt =head while( srt ->info!=data) srt = srt >link srt ->link= srt ->link->link p tr->link=new Algorithm Computer Science & Engineering , KUET 28/43 Algorithm

30. Deleting after a given value link data A X B link link data data C Computer Science & Engineering , KUET 29/43 srt head C

31. Deleting before a given value Declare nodes srt , temp and prev Search the element to delete before Update link of the previous node with the link of the next node Node * srt , *temp, * prev srt =head while( srt ->info!=data) srt = srt >link prev = temp; temp = srt ; Prev ->link = srt Algorithm Computer Science & Engineering , KUET 30/43 Algorithm

32. Deleting before a given value link data A B link link data data C Computer Science & Engineering , KUET 31/43 prev head X D link data temp srt

33. Deleting a given value Declare nodes srt and temp Search the element to delete Update link of the previous node with the link of the selected node Node * srt , *temp Srt =head while( srt ->info!=data) srt = srt ->link temp = srt ; temp->link = srt ->link Algorithm Computer Science & Engineering , KUET 32/43 Algorithm

34. Deleting after a given value link data A B link link data data C Computer Science & Engineering , KUET 33/43 head X D link data temp srt

35. Operations on a singly circular linked list The basic operations on singly circular linked lists are : Creation Insertion Deletion Traversing Searching Computer Science & Engineering , KUET 34/43

36. Operations on a singly circular linked list Creation of a circular linked list is same as singly list except that we will have to use head instead of NULL To traverse the list we have to start from head and end until the link of a node is head To insert a node at the beginning of the list we have to store the value of head in a temporary node and operate accordingly Computer Science & Engineering , KUET 35/43 The operations on a singly circular linked is almost same as that of a singly linked list. The only difference between them is that the link of the last node of a singly linked list contains NULL, whereas that of a circular list contains head

37. Operations on a singly circular linked list The operation insert last, is almost the same as that of the singly list, difference: head instead of NULL in the link of new node The operation insert after, is same as that of the singly list. If the node is the last node then we can perform the operation just by calling the insert last’s function The operation insert before, is same as that of the singly list The operation delete after and before, is same as that of the singly list. Deleting last element is also almost the same, only have to update the link of previous node with head. But the process of deleting the first element is different, it’ll be discussed in this presentation The operation delete element, is same as that of the singly list Computer Science & Engineering , KUET 36/43

38. Operations on a singly circular linked list Most of the operations are almost the same as singly linked list incase of a singly circular linked list, only a little variation in list creation and deleting the first element, next contents contain these operations! Computer Science & Engineering , KUET 37/43

39. Allocate a new node Insert new element Make new node point to head Update head to point to new node of first element If not first element update link of previous element with current node address Algorithm create a new node new->data=item new-> link=head head=new, temp=new, if head==NULL e lse temp->link=new, temp= ptr Creation of a circular list Computer Science & Engineering , KUET 38/43

40. Creation head New Node A Computer Science & Engineering , KUET 39/43 head head B New Node new->data=item new->link=head

41. Deleting the first node Declare a new node, srt Assign head to the new node Update head with the link of the new node Update the link of last node with the link of the new node Algorithm srt =head head= srt ->link last->link=head Computer Science & Engineering , KUET 40/43

42. Deleting the first node head link link data data head d ata link B C A Computer Science & Engineering , KUET 41/43 last head= srt ->link last->link=head

43. Application Linked lists are used in many other data structures. Linked lists are used in polynomial manipulation. Representation of trees, stacks, queues. etc . Computer Science & Engineering , KUET 42/43

44. Disadvantages of Linked Lists The memory is wasted as pointers require extra memory for storage. No element can be accessed randomly. I t has to access each node sequentially. Reverse Traversing is difficult in linked list . No binary search. Computer Science & Engineering , KUET 43/43

45. Questions? 

46. Thank you 