PROGRAMMING 622 Presentation - Lecture 5.pptx

Presentation about c++ Stacking.

1. Richfield PROGRAMMING 622 LINKED LISTS Lecture 5

2. Introduction to Linked Lists Linked list : A list of items, called nodes, in which the order of the nodes is determined by the address, called the link, stored in each node. Every node in a linked list has two components Data – stores the relevant information Link - stores the address of the next node in the list. Every node (except the last node) contains the address of the next node. The address of the first node in the list is stored in a separate location, called the head or first .

3. Introduction to Linked Lists Remember Vectors and Deques? To Insert a New Element: 10 20 30 40 50 10 20 30 40 50 25

4. Introduction to Linked Lists Elements need to be shifted to accommodate for new element So, The New Vector/Deque: 10 20 30 40 50 25 10 20 25 30 40 50

5. Introduction to Linked Lists The same is true for Deletion, Elements need to be shifted to accommodate for deleted element So, The New Vector/Deque: 10 20 25 40 50 10 20 25 30 40 50 10 20 25 40 50

6. Introduction to Linked Lists So , What’s The Problem With This? Insertion and Deletion operations are generally inefficient in these structures, especially when they occur in the middle (Larger sized vectors/deques require a lot of shifting)

7. Introduction to Linked Lists To overcome this inefficiency, we introduce linked lists. * Arrows represent memory addresses, which are in binary head 10 20 30 NULL

8. Introduction to Linked Lists So now when inserting: head 10 20 30 NULL 15

9. Introduction to Linked Lists So now when inserting: head 10 20 30 NULL 15

10. Introduction to Linked Lists So now when inserting: head 10 20 30 NULL 15

11. Introduction to Linked Lists And when deleting: head 10 20 30 NULL 15

12. Introduction to Linked Lists And when deleting: head 10 20 30 NULL 15

13. Introduction to Linked Lists And when deleting: head 10 20 30 NULL 15

14. Introduction to Linked Lists And when deleting: head 10 20 30 NULL 15

15. Structure of the Node Remember! Every node in a linked list has two components Data – stores the relevant information Link - stores the address of the next node in the list. To Declare a node:

16. Traversing a Linked List head 10 20 30 NULL 15 current

17. Traversing a Linked List head 10 20 30 NULL 15

18. Traversing a Linked List head 10 20 30 NULL 15

19. Traversing a Linked List head 10 20 30 NULL 15

20. Traversing a Linked List head 10 20 30 NULL 15

21. Traversing a Linked List To traverse a linked list, it is essential to use a separate pointer, typically named `current`, to preserve the integrity of the list. This approach ensures that the starting point of the list is not lost while keeping track of the current position within the traversal. Code Example of traversing a linked list:

22. To Summarize Everything Declaring A Node:

23. To Summarize Everything Traversing A Linked List:

24. To Summarize Everything Inserting into a Linked List:

25. To Summarize Everything Deleting From a Linked List:

26. To Summarize Everything Using These Functions:

27. Thank you