CSC 1061 Week 10 LinkList and Templates PDF

CSC 1061 LINKLIST DATA STRUCTURE  OBJECTIVES AGENDA: WEEK 10 Design, implement and test collection 1. Overview of Linklist classes that use linked lists underlying to store a collection of elements...

CSC 1061 LINKLIST DATA STRUCTURE  OBJECTIVES AGENDA: WEEK 10 Design, implement and test collection 1. Overview of Linklist classes that use linked lists underlying to store a collection of elements 2. Friend classes Use a node class to create and manipulate 3. std::List | Doubly LinkList the linked list 4. Node class & LinkList class Analyze problems that can be solved with 5. Constructor | isEmpty linked lists and when appropriate propose 6. append | removeFirst | free alternatives to simple linked lists such as double linked lists and lists with dummy 7. LinkList Traversal nodes 8. RemoveByItem Understand the trade-offs between 9. LinkList File IO member dynamic arrays and linked lists functions Give LinkList access to Node private members implementing friend class PREVIEW: WHAT ARE LINKED STRUCTURES Read the explanation of 4.2 What Are Linked Structures? Watch the 2nd YouTube: Linked List by Slim Pickin's within the tutorial LINKLIST DATA STRUCTURE OVERVIEW A linked list data structure includes a series of connected nodes. Main advantage data is NOT contained in contiguous memory. Flexible memory allows for fast insertion and better overall iteration Linked list can be used as the basis for other containers: queue / stack head 0x4b 0x72 0xe9 first begin data data data 0x4b next = 0x72 next = 0xe9 next = 0x0 STD::LIST (CPLUSPLUS.COM) std::list containers are implemented as doubly-linked lists Doubly linked lists store each element in a node that is linked together in non-contiguous memory Each node contains a link preceding node and a link next node 0x4b 0x72 0xe9 data data data next = 0x72 next = 0xe9 next = 0x0 head 0x4b previous = 0x0 previous = 0x4b previous = 0x72 tail 0xe9 DOUBLY LINKLIST The doubly linked list allow for fast node erasure, faster fetching of end nodes, and more flexible iteration. At the cost of flexibility of the doubly-linked list, it generally costs more memory to use. In large lists, consider the idea of a node being twice the size as normal. In the case that you have no reason to iterate backwards, the doubly-linked list can be considered inefficient and cumbersome managing twice the pointers! SINGLE, FORWARD LINKLIST A singly-linked list iterates forward Visualize: https://www.cs.usfca.edu/~galles/visualization/QueueLL.html 0x4b 0x72 0xe9 head data data data 0x4b next = 0x72 next = 0xe9 next = 0x0 HELPER CLASS: NODE Node Class is: The structure of the element object being stored in the LinkList Encapsulates: Address of Node data item pointer to the next Node* data Node class is: NOT Dynamic! *next NO allocation of memory NO deallocation of memory NOT A container – NO adding, NO removing, etc. FRIEND CLASSES (CPLUSPLUS) A friend class's members have access to the private or protected members of another class. In the example, Rectangle is considered a friend class by Square, but Square is NOT considered a friend by Rectangle. Therefore, the member functions of Rectangle can access the protected and private members of Square, but not the other way around. Another property of friendships is that they are not transitive: The friend of a friend is not considered a friend unless explicitly specified. LINKLIST DATA STRUCTURE The LinkList class is a single, one-directional, linear data structure A container of Nodes that are allocated on the heap at runtime Dynamically allocates a new Node* each time an item added / appended / inserted Dynamically deallocates the Node each time an item is removed / erased 0x4b 0x72 0xe9 Encapsulates: head: Node* pointer data data data tail: Node* pointer next = 0x72 next = 0xe9 next = 0x0 head 0x4b tail 0xe9 LINKLIST CONSTRUCTOR | ISEMPTY All data structure containers start empty. head 0X0 Constructor: head = tail = nullptr; tail 0x0 Checking to see if a LinkList is empty? Check first pointer doesn't point anywhere. bool isEmpty(): if head == nullptr Why can't we check: return true if head == tail else return false  LINKLIST::APPEND WHEN EMPTY To append an element at the end, a new Node must be allocated and then inserted into the LinkList, connecting the links ptr 0x4b 1 0x4b (1) ptr: alloc new Node and set data (2) if isEmpty() head 0x0 data:A 2 (3)head and tail assigned to ptr tail 0x0 next:0x0 3 head 0x4b tail 0x4b 3  LINKLIST::APPEND NOT EMPTY 0x4b 0x72 0x72 1 head 0x4b ptr data:A data:B tail 0x4b next:0x0 next:0x0 (1) ptr alloc new Node and set data if isEmpty() head and tail assigned to Node 0x4b head 0x4b else // NOT empty data:A (2) tail->next = ptr tail 0x72 3 next:0x72 2 (3) tail assigned to ptr  LINKLIST::REMOVE_FIRST tmp 0x4b 1 0x4b Scenario: one item (1) set tmp to point to first head 0x0 2 if not isEmpty() and head == tail 3 tail 0x0 (2) delete tmp (3) head = tail = nullptr else if not isEmpty() 1 tmp 0x4b (2) head = tmp->next 0x4b 0x72 head 0x72 2 (3) delete tmp data: B 3 next:0x0 Scenario: more than one tail 0x72  while not isEmpty() LINKLIST::FREE removeFirst() 0x4b 0x72 0xe9 head 0x4b data: B data: C tail next:0xe9 next:0x0 Iteration #1 0xe9 0x72 0xe9 head 0x72 data: C Iteration #2 next:0x0 tail 0xe9 head 0X0 0xe9 Iteration #3 tail 0X0 REVIEW TRAVERSING THROUGH A BAG for(int i = 0 ; i < size ; i++ ) { std::cout next) } class LinkList { Node* head; Linklists are NOT stored in contiguous memory, Node* tail; and cannot use indexes and MUST use pointers }; to traverse from one memory location to the next head 0x4b 0x4b 0x72 0xe9 listObj data = A data = B data = C tail 0xe9 next = 0x72 next = 0xe9 next = 0x0  LINKLIST::REMOVE_BY_ITEM ALGORITHM Check for empty list: if(isEmpty()) return; If data item is first Node, then call removeFirst if(item == head->data) removeFirst(); else 1. Traverse through and find the previous Node to the Node with the data item that you want to remove 2. Set a temporary pointer to point to the Node to remove 3. Move the previous pointer next link around the Node you want to remove 4. delete the Node to remove (special instructions if it is the last node needed)  LINKLIST::REMOVE_BY_ITEM: MIDDLE 0x4b 0x72 0x2d 0xe9 head 0x4b data: A data: B data: C 4 data: D next = 0x72 next = 0x2d next: 0xe9 next = 0x0 tail 0xe9 3 1 if data item found: prev 0x72 (1) Traverse and find previous Node* to the one to delete (2) Set tmp to point to one after previous tmp = prev->next tmp 0x2d 2 (3) Move prev->next around tmp: prev->next = tmp->next (4) delete tmp Do NOT forget the special instructions when removing the last node LINKLIST FILE IO MEMBER FUNCTIONS readFile - reading from a file does NOT change for different data structures. while ( fileRead >> tempObject ) { append( tempObject ); } writeFile – writing to a file changes based upon the traversal for ( Node* cursor = head ; cursor != nullptr ; cursor = cursor->next) { fileWrite data; } POST REVIEW Complete the 4.12 Matching Activity