Linked lists are linear data structures .pptx

Linked lists are linear data structures where elements are linked using pointers. The three main types are singly, doubly, and circular linked lists.

1. Linked List ADT

2. Introduction Fixed-size data structures Arrays, structs Dynamic data structures Grow and shrink as program runs Linked lists Insert/remove items anywhere

3. Self-Referential Data Structures Self-referential data structure Has pointer to variable (object) of same data type Link together to form useful data structures Lists, stacks, queues, trees Terminated with NULL pointer 15 10 NULL pointer (points to nothing) Data member and pointer

4. Self-Referential Data Structures Example Code struct ListNode { int data; ListNode *next; }; ListNode *ListHeadPtr;

5. Linked Lists H D Q firstPtr ... D T

6. Linked Lists Linked lists vs. arrays Arrays can become full Allocating "extra" space in array wasteful, may never be used Linked lists can grow/shrink as needed Linked lists only become full when system runs out of memory Linked lists can be maintained in sorted order Insert element at proper position Existing elements do not need to be moved

7. Linked List Operations Selected linked list operations Insert node at start Insert node at end Remove node from start Remove node from end Remove specific node Searching specific node Displaying all nodes

8. Insert at start (head) 7 11 firstPtr 12 newPtr a) 7 11 firstPtr 12 newPtr b) newPtr->nextPtr = firstPtr firstPtr = newPtr If list empty, then firstPtr = lastPtr = newPtr

9. Insertion at end (tail) Need to traverse whole list and find address of last node Once address of last node is known, new node can be appended at end of list Problem: Not efficient: needs whole list traversal Solution: Use another pointer, must be updated after each insertion at tail

10. Insertion at end (tail) firstPtr lastPtr a) newPtr firstPtr lastPtr b) newPtr 12 7 11 5 12 11 5 7 lastPtr->nextPtr = newPtr lastPtr = newPtr If list empty, then firstPtr = lastPtr = newPtr

11. Remove Node from (start) head firstPtr lastPtr a) firstPtr lastPtr b) tempPtr 12 7 12 12 7 5 11 5 11 tempPtr = firstPtr firstPtr = firstPtr->next; If there are no more nodes, firstPtr = lastPtr = NULL; delete tempPtr;

12. Remove from tail 5 5 11 7 7 12 12 firstPtr lastPtr a) firstPtr lastPtr b) tempPtr currentPtr 11 tempPtr = lastPtr "Walk" list until get next-to-last node, until currentPtr->nextPtr = lastPtr lastPtr = currentPtr delete tempPtr

13. Linked Lists Node data Data for each node Link to next node Start pointer How to implement a Linked List structure using a class? Suggestions??