Data Structure Podcast PDF

2.1, 2.2, 2.3 2.1 List abstract data type List abstract data type A list is a common ADT for holding ordered data, having operations like append a data item, remove a data item, search whether a data item exists, and print the list. Ex: For a given list item, after "Append 7", "Append 9", and "Appe...

2.1, 2.2, 2.3 2.1 List abstract data type List abstract data type A list is a common ADT for holding ordered data, having operations like append a data item, remove a data item, search whether a data item exists, and print the list. Ex: For a given list item, after "Append 7", "Append 9", and "Append 5", then "Print" will print (7, 9, 5) in that order, and "Search 8" would indicate item not found. A user need not have knowledge of the internal implementation of the list ADT. Examples in this section assume the data items are integers, but a list commonly holds other kinds of data like strings or entire objects. Operation Description Example starting with list: 99, 77 Append(list, x) Inserts x at end of list Append(list, 44), list: 99, 77, 44 Prepend(list, x) Inserts x at start of list Prepend(list, 44), list: 44, 99, 77 InsertAfter(list, w, x) Inserts x after w InsertAfter(list, 99, 44), list: 99, 44, 77 Remove(list, x) Removes x Remove(list, 77), list: 99 Search(list, x) Returns item if found, else Search(list, 99), returns item 99 returns null Search(list, 22), returns null Print(list) Prints list's items in order Print(list) outputs: 99, 77 PrintReverse(list) Prints list's items in reverse PrintReverse(list) outputs: 77, 99 order Sort(list) Sorts the lists items in list becomes: 77, 99 ascending order IsEmpty(list) Returns true if list has no For list 99, 77, IsEmpty(list) items returns false  GetLength(list) Returns the number of items GetLength(list) returns 2 in the list 2.2 List data structure A common approach for implementing a linked list is using two data structures: 1.​ List data structure: A list data structure is a data structure containing the list's head and tail, and may also include additional information, such as the list's size. 2.​ List node data structure: The list node data structure maintains the data for each list element, including the element's data and pointers to the other list element. A list data structure is not required to implement a linked list, but offers a convenient way to store the list's head and tail. When using a list data structure, functions that operate on a list can use a single parameter for the list's data structure to manage the list. A linked list can also be implemented without using a list data structure, which minimally requires using separate list node pointer variables to keep track of the list's head. A linked list has O(n) space complexity, whether a list data structure is used or not. If a list data structure is used, O(1) space is needed for the single list data structure. O(n) + O(1) = O(n). 2.3 Singly-linked lists Singly-linked list data structure A singly-linked list is a data structure for implementing a list ADT, where each node has data and a pointer to the next node. The list structure typically has pointers to the list's first node and last node. A singly-linked list's first node is called the head, and the last node the tail. A singly-linked list is a type of positional list: A list where elements contain pointers to the next and/or previous elements in the list. null null is a special value indicating a pointer points to nothing. The name used to represent a pointer (or reference) that points to nothing varies between programming languages and includes nil, nullptr, None, NULL, and even the value 0. Appending a node to a singly-linked list Given a new node, the Append operation for a singly-linked list inserts the new node after the list's tail node. Ex: ListAppend(numsList, node 45) appends node 45 to numsList. The notation "node 45" represents a pointer to a node with a data value of 45. This material does not discuss language-specific topics on object creation or memory allocation. The append algorithm behavior differs if the list is empty versus not empty: ​ Append to empty list: If the list's head pointer is null (empty), the algorithm points the list's head and tail pointers to the new node. ​ Append to non-empty list: If the list's head pointer is not null (not empty), the algorithm points the tail node's next pointer and the list's tail pointer to the new node. Prepending a node to a singly-linked list Given a new node, the Prepend operation for a singly-linked list inserts the new node before the list's head node. The prepend algorithm behavior differs if the list is empty versus not empty: ​ Prepend to empty list: If the list's head pointer is null (empty), the algorithm points the list's head and tail pointers to the new node. ​ Prepend to non-empty list: If the list's head pointer is not null (not empty), the algorithm points the new node's next pointer to the head node, and then points the list's head pointer to the new node. 2.4, 2.5, 2.6 2.4 Singly-linked lists: Insert Given a new node, the InsertAfter operation for a singly-linked list inserts the new node after a provided existing list node. curNode is a pointer to an existing list node, but can be null when inserting into an empty list. The InsertAfter algorithm considers three insertion scenarios: ​ Insert as list's first node: If the list's head pointer is null, the algorithm points the list's head and tail pointers to the new node. ​ Insert after list's tail node: If the list's head pointer is not null (list not empty) and curNode points to the list's tail node, the algorithm points the tail node's next pointer and the list's tail pointer to the new node. ​ Insert in middle of list: If the list's head pointer is not null (list not empty) and curNode does not point to the list's tail node, the algorithm points the new node's next pointer to curNode's next node, and then points curNode's next pointer to the new node. ListInsertAfter(list, curNode, newNode) { if (list⇢head == null) { // List empty list⇢head = newNode list⇢tail = newNode } else if (curNode == list⇢tail) { // Insert after tail list⇢tail⇢next = newNode list⇢tail = newNode }  else { newNode⇢next = curNode⇢next curNode⇢next = newNode } } 2.5 Singly-linked lists: Remove Given a specified existing node in a singly-linked list, the RemoveAfter operation removes the node after the specified list node. The existing node must be specified because each node in a singly-linked list only maintains a pointer to the next node. The existing node is specified with the curNode parameter. If curNode is null, RemoveAfter removes the list's first node. Otherwise, the algorithm removes the node after curNode. ​ Remove list's head node (special case): If curNode is null, the algorithm points sucNode to the head node's next node, and points the list's head pointer to sucNode. If sucNode is null, the only list node was removed, so the list's tail pointer is pointed to null (indicating the list is now empty). ​ Remove node after curNode: If curNode's next pointer is not null (a node after curNode exists), the algorithm points sucNode to the node after curNode's next node. Then curNode's next pointer is pointed to sucNode. If sucNode is null, the list's tail node was removed, so the algorithm points the list's tail pointer to curNode (the new tail node). ListRemoveNodeAfter(list, curNode) { // Special case, remove head if (curNode is null && list⇢head is not null) { sucNode = list⇢head⇢next list⇢head = sucNode if (sucNode is null) { // Removed last item list⇢tail = null  } } else if (curNode⇢next is not null) { sucNode = curNode⇢next⇢next curNode⇢next = sucNode if (sucNode is null) { // Removed tail list⇢tail = curNode } } } 2.6 Linked list search Given a key, a search algorithm returns the first node whose data matches that key, or returns null if a matching node was not found. A simple linked list search algorithm checks the current node (initially the list's head node), returning that node if a match, else pointing the current node to the next node and repeating. If the pointer to the current node is null, the algorithm returns null (matching node was not found). Start 2x speed ListSearch(list, key) { curNode = list⇢head while (curNode is not null) { if (curNode⇢data == key) { return curNode } curNode = curNode⇢next } return null }