Linked list module full chapter sujruejejej

Linked list module full chapter sujruejejej

1. Chandigarh Group of Colleges, Landran
MODULE 3
LINKED LIST

2. Chandigarh Group of Colleges, Landran
LINKED LIST Definition:
•Alinked listis a linear data structure where each element is a
separate object.
•Linked listelements are not stored at contiguous location; the
elements arelinkedusing pointers.
•LINKED LIST is a collection of data elements called nodes
where the linear order is given by means of pointer.
•Each node of alistis made up of two items -the data and a
reference to the next node.
•The last node has a reference to null.

3. Chandigarh Group of Colleges, Landran
Representation of a node:

4. Chandigarh Group of Colleges, Landran

5. Chandigarh Group of Colleges, Landran
Representation of Linear Linked List:

6. Chandigarh Group of Colleges, Landran
Example of linked list :

7. Chandigarh Group of Colleges, Landran
Example of Linked List:

8. Chandigarh Group of Colleges, Landran
Example of linked list :

9. Chandigarh Group of Colleges, Landran
Example of LINKED List:

10. Chandigarh Group of Colleges, Landran
Representation in Memory:

11. Chandigarh Group of Colleges, Landran
PRACTICE QUESTION
INFO LINK
1
2
3
4
5
A
A
P
K
L
5
4
1
X
2
START
3

12. Chandigarh Group of Colleges, Landran
Types of Linked list:
•Linear or Single linked list
•Circular Linked List
•Two way or Doubly Linked list

13. Chandigarh Group of Colleges, Landran
Singly or Linear linked list
VS
Circular Linked List:

14. Chandigarh Group of Colleges, Landran
Single or Linear linked list
VS
Double Linked List:

15. Chandigarh Group of Colleges, Landran
Operations on Linear Linked List:
1. Traversing:
•ALGORITHM:-
TRAVERSE( LIST, START , PTR, INFO , LINK)
LIST is linear linked list stored in memory, START Pointer points to
first node, PTR is pointer that points to the node currently being
processed, INFO contains data elements and LINK that stores the
address of next node.
1.Set PTR:=START. [Initializes pointer PTR]
2.Repeat steps 3 and 4 while PTR!=NULL.
3.Apply PROCESS to INFO[PTR].
4.Set PTR:=LINK[PTR].[PTR now points the next node].
[End of step 2 loop]
5.Exit.

16. Chandigarh Group of Colleges, Landran
TRAVERSING A LINKED LIST EXAMPLE:

17. Chandigarh Group of Colleges, Landran
TRAVERSING A LINKED LIST EXAMPLE:

18. Chandigarh Group of Colleges, Landran
TRAVERSING SOLVED EXAMPLE 1:

19. Chandigarh Group of Colleges, Landran
TRAVERSING SOLVED EXAMPLE 1 contd:

20. Chandigarh Group of Colleges, Landran
TRAVERSING SOLVED EXAMPLE 2 :

21. Chandigarh Group of Colleges, Landran
TRAVERSING SOLVED EXAMPLE 2 contd:

22. Chandigarh Group of Colleges, Landran
2
L
H
O
E
R
L
D
O
L
W
8
4
5
6
9
1
X
10
7
3
TRAVERSING SOLVED EXAMPLE 3 :
START
INFO LINK
1
2
3
4
6
7
8
9
10
5

23. Chandigarh Group of Colleges, Landran
TRAVERSING SOLVED EXAMPLE 3 contd:

24. Chandigarh Group of Colleges, Landran
TRAVERSING SOLVED EXAMPLE 3 contd: