ds05linkedlists.pdf

CS121 Data Structures C Linked Lists Monika Stepanyan [email protected] Fall 2024 Important Data and Statistics 1 I of the semester passed! 5 I 23 classes remaining I 22 days till the Midterm exam I I 70 days till the Thanksgiving Break...

CS121 Data Structures C Linked Lists Monika Stepanyan [email protected] Fall 2024 Important Data and Statistics 1 I of the semester passed! 5 I 23 classes remaining I 22 days till the Midterm exam I I 70 days till the Thanksgiving Break I HW1 due Wednesday, October 2, 23:59 Adding an Array Entry To add an entry e into array board at index i, we need to make room for it by shifting forward the n − i entries board[i],... , board[n − 1] board 0 1 2 i n board 0 1 2 i n board e 0 1 2 i n Removing an Array Entry To remove the entry e at index i, we need to fill the hole left by e by shifting backward the n − i − 1 elements board[i + 1],... , board[n − 1] board e 0 1 2 i n board 0 1 2 i n board 0 1 2 i n Arrays: Advantages and Disadvantages Drawbacks of array as an ordered data structure: I fixed capacity I expensive insertions and deletions at interior positions (shifting many elements) Advantages of the array: I Constant-time access to any element Singly Linked Lists Linked list provides an alternative to an array-based structure. A linked list is a collection of nodes that collectively form a linear sequence. In a singly linked list, each node stores: next I a reference to an object that is an element of the sequence I a reference to the next node of the list element node head  Linked List Terms The linked list instance must keep a reference to the first node of the list, known as the head. The last node of the list is known as the tail. Traversing the linked list—starting at the head and moving from one node to another by following each node’s next reference. The tail has null as its next reference. Commonly, a reference to the tail node is also stored, as is the count of the total number of nodes in the list (its size). Inserting at the Head Algorithm addFirst(e): newest = Node(e) {create new node instance storing reference to element e} newest.next = head {set new node’s next to reference the old head node} head = newest {set variable head to reference the new node} size = size + 1 {increment the node count} Inserting at the Tail Algorithm addLast(e): newest = Node(e) {create new node instance storing reference to element e} newest.next = null {set new node’s next to reference the null object} tail.next = newest {make old tail node point to new node} tail = newest {set variable tail to reference the new node} size = size + 1 {increment the node count} Removing from the Head Algorithm removeFirst: if head == null then the list is empty. head = head.next {make head point to next node (or null)} size = size − 1 {decrement the node count} Removing from the Tail Removing from the tail of a singly linked list is not efficient! There is no constant-time way to update the tail to point to the previous node Interface of a Singly Linked List size() Returns the number of elements in the list. isEmpty() Returns true if the list is empty, and false otherwise. first() Returns (but does not remove) the first element in the list. last() Returns (but does not remove) the last element in the list. addFirst(e) Adds a new element to the front of the list. addLast(e) Adds a new element to the end of the list. removeFirst() Removes and returns the first element of the list. Singly Linked List Implementation: Node Singly Linked List Implementation I Singly Linked List Implementation II Circularly Linked Lists There are applications in which data can be viewed as having a cyclic order, with well-defined neighbouring relationships, but no fixed beginning or end. A circularly linked list is a singularly linked list in which the next reference of the tail node is set to refer back to the head of the list (rather than null). Rotating We no longer explicitly maintain the head reference. Thus we save a bit on memory usage and make the code simpler and more efficient. When rotating the linked list, we simply advance the tail reference to point to the node that follows it. Adding at the Head/Tail Add at the head: Add at the tail: add at the head and immediately rotate Circularly Linked List Implementation I Circularly Linked List Implementation II Doubly Linked Lists Limitations of singly linked list: I unable to efficiently delete a node at the tail I cannot efficiently delete a node from an interior position if given a reference to it (cannot determine the preceding node) In a doubly linked list each node keeps an explicit reference to the node before it and a reference to the node after it. A doubly linked list can be traversed forward and backward. In a doubly linked list, each node stores: I a reference to an object that is an prev next element of the sequence I a reference to the previous node of the list element node I a reference to the next node of the list Header and Trailer Sentinels It helps to add special nodes at both ends of the list: I a header node at the beginning of the list I a trailer node at the end of the list These ‘dummy’ nodes are known as sentinels (or guards). They do not store elements. header nodes/positions trailer elements Insertion Every insertion takes place between a pair of existing nodes. p A B C p A B q C X p q A B X C Deletion Every deletion takes place between a pair of existing nodes. p A B C D A B C p D A B C Interface of a Doubly Linked List size() Returns the number of elements in the list. isEmpty() Returns true if the list is empty, and false otherwise. first() Returns (but does not remove) the first element in the list. last() Returns (but does not remove) the last element in the list. addFirst(e) Adds a new element to the front of the list. addLast(e) Adds a new element to the end of the list. removeFirst() Removes and returns the first element of the list. removeLast() Removes and returns the last element of the list. Doubly Linked List Implementation: Node Doubly Linked List Implementation I Doubly Linked List Implementation II Doubly Linked List Implementation III Summary Reading Sections 3.2–3.6 of the main textbook Questions?