Linked List, basics , types , operations

Presentation on types of Linked List , various operations on it

1. Linked List

2. Introduction A linked list is a data structure in which Successive elements are connected by pointers. Last element points to NULL . It can grow or shrink in size during execution of a program. 2 A B C head

3. 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.

4. Array vs Linked list

5. Creating a node

6. To be called from main as

7. Types of Linked list 3 types Singly Linked List(SLL) Doubly Linked List(DLL) Circular Linked List(CLL)

8. Insertion in a SLL 3cases in this Insertion at the beginning Insertion at the end Insertion after a particular node

9. Insertion in a SLL Insertion at the beginning Step 1:- Make the new ptr of the node point towards the first node of the list Step2:- Make the head ptr point towards this new node * If the list is empty(means this is gng to be the 1 st node then, simply make head ptr point towards new node )

10. Insertion in a SLL Insertion at the beginning

11. Insertion in a SLL Insertion at the end Simply need to make the next ptr of the last node point to the new node instead of NULL

12. Insertion in a SLL Insertion at the end

13. Insertion in a SLL Insertion after a particular node Step 1:- Make the next ptr of the node to be inserted point to the next node of the node before which you wanna insert the node Step2:- Make the next ptr of the node after which the node is to be inserted ,point to the node to be inserted

14. Insertion in a SLL Insertion after a particular node

15. Deletion in a SLL

16. Deletion in a SLL 3cases in this Deletion from the beginning Deletion from the end Deletion of an intermediate node

17. Deletion in a SLL Deleting the first node in SLL Step 1:- Make the start ptr point towards the 2 nd node Step2:- Deleting the 1 st node using DELETE keyword.

18. Deletion in a SLL Deleting the first node in SLL

19. Deletion in a SLL Deleting the last node in SLL Step 1:- Make the second last node’s next ptr point to NULL Step2:- Deleting the last node using DELETE keyword.

20. Deletion in a SLL Deleting the last node in SLL

21. Deletion in a SLL Deleting a particular node in SLL Step 1:- Make the next ptr of the node previous to the node being deleted point to the successor node of the node to be deleted Step2:- Deleting the particular node using DELETE keyword.

22. Deletion in a SLL Deleting a particular node in SLL

23. Searching in a SLL

24. Searching in a SLL Finding required element in the list 2 ways Linear Much easier in case of linked list Binary Complex as random traversal is not easy

25. Linear search in a SLL Each node is traversed till the data in the node matches with the required value.

26. Doubly Linked List

27. Doubly Linked List Linked data structure that consists of a set of sequentially linked records called nodes Contains 3 fields An integer value Link to the next node Link to the previous node

28. Structure of a DLL

29. Traversing in a DLL

30. Searching in a DLL

31. Insertion in a DLL

32. Doubly Linked List--Insertion Insertion at the beginning Node to be added Existing linked list

33. Doubly Linked List--Insertion Insertion at the beginning 1 st step:- Make it point to head

34. Doubly Linked List--Insertion Insertion at the beginning 2 nd step:- make prev point to temp

35. Doubly Linked List—Insertion at beginning

36. Insertion at the beginning in a DLL

37. Insertion at the end in a DLL 1 st step:- Traverse the list Update next part of last node Update prev part of temp node How to do this?

38. Insertion at the end in a DLL 1 st step:- take a pointer tp which initially points to 1 st node and later last node Code for tp to traverse each node

39. Insertion at the end in a DLL tp is now pointing the last node using the code--- traversal done

40. Insertion at the end in a DLL Step 2:- Attach a new node to end node of the list Step:- make this point to prev of temp node code

41. Insertion at the end in a DLL

42. Insertion at the end in a DLL

43. Insertion at the end in a DLL

44. Insertion at the end in a DLL

45. Insertion after a node in a DLL

46. Insertion after a node in a DLL 4000 newP There must be a pointer pointing to this new node We need a ptr pointing to this 2 nd node

47. Insertion after a node in a DLL temp will point to the 2 nd node as per this code

48. Insertion after a node in a DLL Now we have pointers pointing position node and after node of the desired location to insert

49. Insertion after a node in a DLL Make this ptr point to prev of new node code

50. Insertion after a node in a DLL Now prev part of this node needs to point next of new node code

51. Insertion after a node in a DLL Prev of this node points to next of temp and next of this node points to prev of temp2 code

52. Insertion after a node in a DLL

53. Insertion after a node in a DLL

54. Deletion in a DLL

55. Deletion from beginning in a DLL

56. Deletion from beginning in a DLL Step1:-Let a temp node point the head node

57. Deletion from beginning in a DLL Step2:- let head point to next node now code

58. Deletion from beginning in a DLL Step:-Remove the temp node

59. Deletion from beginning in a DLL Step:- Assign NULL to temp and prev of head node

60. Deletion from beginning in a DLL Method 2

61. Deletion from beginning in a DLL

62. Deletion from particular position in a DLL

63. Deletion from a particular position in a DLL Initially temp is pointing to head and moving towards the position to be deleted

64. Deletion from a particular position in a DLL Step:- take 1 more ptr to point to node previous to temp

65. Deletion from a particular position in a DLL Step:- next of temp2 should now point to next of temp

66. Deletion from a particular position in a DLL Step:- update this so that it points to next of temp2

67. Deletion from a particular position in a DLL Step:- free memory of temp pointer

68. Deletion from a particular position in a DLL

69. Deletion from a particular position in a DLL

70. Delete last node from a DLL

71. Delete last node from a DLL Traverse the list till last using temp pointer

72. Delete last node from a DLL Step:- storing this node in a temp2 While(temp-> NEXT !=NULL) { temp = temp->NEXT; } temp2 = temp-> prev ; temp2->NEXT = NULL; Step:-Now this should point to NULL

73. Delete last node from a DLL While(temp-> NEXT !=NULL) { temp = temp->NEXT; } temp2 = temp-> prev ; temp2->NEXT = NULL; free(temp); temp=NULL;

74. Delete last node from a DLL

75. Delete last node from a DLL

76. Circular Linked List

77. Circular Linked List Variation of LL in which last element points to 1 st element Both SLL and DLL can be converted to CLL.

78. Singly Linked List as Circular In SLL , the next pointer of last node points to 1 st node

79. Doubly Linked List as Circular In DLL , the nest pointer of last node points to 1 st node and previous pointer of 1 st node points to last node making the circular in both direction

80. Advantages of CLL 1.Any node can be a starting point.We can traverse the whole list by starting from any point 2.

81. Disadvantages of CLL 1. inserting at start of list would require doing a search for last node ----expensive 2. Finding end of the list and loop control is harder ( no NULL’s to mark the beginning and end )

82. Circular Linked List--Operations Insertion Deletion Display

83. Circular Linked List--Insertion Insertion At the beginning At the end At a particular position

84. Circular Linked List—Insertion at beginning Tail pointer is the pointer to the last node of the linked list Why this tail pointer is needed? Next slide

85. Circular Linked List—Insertion at beginning Consider a CLL of 3 nodes head A ptr is must for this node it’s NEXT can point to new node No need to traverse the whole list to find last node

86. Circular Linked List—Insertion at beginning Step:- Update this ptr Let it point to NEXT ptr of tail

87. Circular Linked List—Insertion at beginning Step:- Update the NEXT of tail ptr

88. Circular Linked List– Insertion at end Step:- update this ptr and let it point to the first node So NEXT ptr of new node takes the current address which tail ptr’s NEXT has (to point the first node)

89. Circular Linked List– Insertion at end Step:- this ptr needs to point to the new node Tail ptr needs to point to new node now Code

90. Circular Linked List– Insertion at end Final result

91. Circular Linked List– Insertion between nodes Initial State

92. Circular Linked List– Insertion between nodes Step:- a ptr is needed to point this node as we need to reach here

93. Circular Linked List– Insertion between nodes Step:- this ptr needs to be updated

94. Circular Linked List– Insertion between nodes Step:- NEXT of this node will point to new node now code

95. Circular Linked List– Insertion between nodes If pos =3(similar to inserting at the end,with slight changes)

96. Circular Linked List--Deletion Deletion At the beginning At the end At a particular position

97. CLL – Deletion of first node

98. CLL – Deletion of first node To delete, we are making a temp ptr point to first node

99. CLL – Deletion of first node code

100. CLL – Deletion of first node Step:- let’s free this node now

101. CLL – Deletion of last node

102. CLL – Deletion of last node For this, we take a temp ptr and make it point to 1 st node initially. This code is to make temp reach the 2 nd node so that we can update the NEXT ptr of this node point to 1000

103. CLL – Deletion of last node The loop has made the temp ptr reach here

104. CLL – Deletion of last node

105. CLL – Deletion of intermediate node

106. CLL – Deletion of intermediate node

107. CLL – Deletion of intermediate node Temp reaches here due to this loop in the code We need something to point to this position So, taking another variable

108. CLL – Deletion of intermediate node Code for setting position of temp2

109. CLL – Deletion of intermediate node

110. CLL – Deletion of intermediate node free(temp2)

111. CLL – Deletion of intermediate node

112. GTU questions Explain creation,insertion and deletion of a doubly linked list with example.[07] Write and explain algorithm for deletion in a singly linked list [07] Write and explain algorithm for insertion in doubly linked list[07] Write an algorithm to insert a node in a circular linked list at the first position[07] Write user defined ‘C’ function to insert node at a specific location in singly linked list[03] Write user defined ‘C’ function to delete node from end in circular linked list[04] Design an algorithm to merge two linked list[07]