I. introduction to linked lists (HR 8.1) A. overview what would we have to do to implement something like Scheme? ------------------------------------------ HR CHAPTER 8 LISTS AND LINKED LISTS Topics: A. pointers and structs B. dynamic data implementation 1. head nodes 2. doubly linked lists 3. circular lists C. Array implementation 1. managing the free store (heap) ------------------------------------------ B. motivation ------------------------------------------ THE PROBLEM Linear, homogeneous, ordered collection. Often inserting and taking items out of from random spots in the collection. ------------------------------------------ What's the problem with using an array for this? What's the big-O complexity of using an array for each insertion? C. singly-linked lists ------------------------------------------ SINGLY-LINKED LISTS PICTURES AND TERMINOLOGY Typical singly-linked list: Inserting after first element: Splicing out third element: def: A *singly-linked list* consists of a collection of ________ called ________, each containing a ______________________, and some data. ------------------------------------------ II. dynamic data implementations of linked lists A. why pointers are needed (HR 8.2) ------------------------------------------ WHY POINTERS? // Wrong.h #include "String.h" struct GuestNode { String name; GuestNode link; // ??? }; // GuestNode.h #include "String.h" struct GuestNode { String name; GuestNode *link; }; typedef GuestNode *GuestPtr; // GuestNode2.h #include "String.h" struct GuestNode; // forward decl. typedef GuestNode *GuestPtr; struct GuestNode { String name; GuestPtr link; }; ------------------------------------------ B. basics of linked list manipulation (HR 8.2) ------------------------------------------ USAGE (C++ DETAILS) // GuestNode.h #include "String.h" struct GuestNode { String name; GuestNode *link; }; typedef GuestNode *GuestPtr; // GuestClient.C #include "GuestNode.h" #include int main() { GuestPtr head = new GuestNode; (*head).name = String("Jones"); head->name = String("Jones"); head->link = new GuestNode; head->link->name = String("Smith"); head->link->link = NULL; return 0; } ------------------------------------------ C. traversals (HR 8.3) ------------------------------------------ PROBLEM Implement the following specification // PrintRegister.h #include #include "GuestNode.h" extern void PrintRegister(GuestPtr head); // PRE: head is a valid pointer // MODIFIES: cout // POST: cout has the names in the // list head added to it, in order // from the head to end, one per line. ------------------------------------------ Why can't you use current++ to go to the link node? can you write that with a recursion? How would you print the list in reverse order? ------------------------------------------ FOR YOU TO DO Implement the following specification // NumGuests.h #include "GuestNode.h" extern int NumGuests(GuestPtr head); // PRE: head is a valid pointer // POST: FCTVAL == the number of guests // in the list starting at head. ------------------------------------------ How is this like Scheme? Can you write IsNull, Car, and Cdr for these lists? How would you write Cons? ------------------------------------------ HIGHER-LEVEL (SCHEME-LIKE) LIST OPS // GuestListOps.h #include "bool.h" #include "GuestNode.h" extern Boolean IsNull(GuestPtr head); // POST: FCTVAL == (head == 0) extern String& Car(GuestPtr head); // MODIFIES: cerr // POST: IF head == 0 // THEN give error and stop program // ELSE return the name cell of head extern GuestPtr& Cdr(GuestPtr head); // MODIFIES: cerr // POST: IF head == 0 // THEN give error and stop program // ELSE return the link cell of head extern GuestPtr Cons(String s, GuestPtr rest); // MODIFIES: cerr // POST: IF can't allocate // THEN give error and stop program // ELSE return pointer to new GuestNode // initialized with s and rest ------------------------------------------ D. insertion (HR 8.4) 1. with head pointer variable as argument ------------------------------------------ PROBLEM (INSERTION INTO LIST) Implement the following specification: // InsertAlphabetic.h #include "GuestNode.h" extern void InsertAlphabetic ( GuestPtr& head, const String & gName); // PRE: head contains a valid pointer // && the list starting at head is // in nondecreasing order. // MODIFIES: head or one element // of the list. // POST: gName is in the list starting // at head && it's still nondecreasing. ------------------------------------------ ------------------------------------------ FOR YOU TO DO Implement the following specification: // Snoc.h #include "GuestNode.h" extern void Snoc ( GuestPtr& head, const String& gName); // MODIFIES: head or one element // of the list. // POST: gName is at the end of the list // starting at head. ------------------------------------------ 2. without head pointer variable as argument ------------------------------------------ PROBLEM Suppose instead of a struct for nodes, we have an object of the class, and can't get a reference to the link member. How to insert? ------------------------------------------ ------------------------------------------ INSERTION INTO LIST WITHOUT HEAD POINTER VARIABLE Implement the following specification: // InsertAlphabetic2.h #include "GuestNode.h" extern void InsertAlphabetic2 ( GuestPtr prevPtr, const String& gName); // PRE: prevPtr contains a valid pointer // && the list starting at prevPtr is // in nondecreasing order // && prevPtr->name <= gName // MODIFIES: one element of the list. // POST: gName is in the list starting // at head && it's still nondecreasing. ------------------------------------------ E. deletion (HR 8.4, pp. 355ff) 1. with head pointer variable as argument ------------------------------------------ PROBLEM (DELETION FROM LIST) Implement the following specification // CheckOut.h #include "GuestNode.h" extern void CheckOut ( GuestPtr& head, const String& gName); // PRE: head contains a valid pointer // && gName is in the list starting // at head (exactly once). // MODIFIES: head or one node of list. // POST: gName is no longer in the // list starting at head && that node is // returned to the free store. ------------------------------------------ How is this different from what you did in the first part of 227? 2. without head pointer variable ------------------------------------------ DELETION FROM LIST WITHOUT HEAD POINTER VARIABLE FOR YOU TO DO Implement the following: // CheckOut2.h #include "GuestNode.h" extern void CheckOut2 ( GuestPtr prevPtr, const String& gName); // PRE: prevPtr is a valid pointer // && gName is in the list following // prevPtr (exactly once). // MODIFIES: one node of list. // POST: gName is no longer in the // list following prevPtr && that node is // returned to the free store. ------------------------------------------ What to do if you want to delete the first node? F. head nodes (HR 8.5) ------------------------------------------ LINKED LISTS WITH HEAD NODES If don't have pointer variable for head, no way to insert before the first node. Solution, have the first node be a dummy "head node", so will always ------------------------------------------ ------------------------------------------ Picture: Cautions: - don't ever delete ------------------------------------------ How do you print such a list? G. doubly-linked and circular lists (8.6) 1. doubly-linked lists ------------------------------------------ PROBLEM Return the node preceeding a given node, want to do this in O(1) time. ------------------------------------------ ------------------------------------------ Solution: doubly linked list // DblGuestNode.h #ifndef DblGuestNode_h #define DblGuestNode_h 1 #include "String.h" struct DblGuestNode { String name; DblGuestNode *nextLink; DblGuestNode *prevLink; }; typedef DblGuestNode *DblGuestPtr; #endif Picture: ------------------------------------------ ------------------------------------------ PROBLEM // InsertAfter.h #include "DblGuestNode.h" extern void InsertAfter(DblGuestPtr prev, const String & gName); // PRE: prev is a legal pointer // && there is enough storage available // MODIFIES: the node pointed at by prev // and the following node, if any // POST: the list following prev has // gName after prev, and then the node // following prev originally, if any // InsertAfter.C #include "InsertAfter.h" #include void InsertAfter(DblGuestPtr prev, const String & gName) { ------------------------------------------ 2. circular lists ------------------------------------------ CIRCULAR LISKED LISTS Convenient for implementing unordered ADTs Problem: need to be careful in traversals! Picture: Variation with tail pointer: ------------------------------------------ in the variation, how do you find the first node? the last? What ADT would this be useful in implementing? Can you have a doubly-linked circular list? III. array implementations of linked lists (HR 8.7) A. motivation ------------------------------------------ WHY STUDY LINKED LISTS IMPLEMENTED BY ARRAYS? - Shows that linked lists aren't exclusively implemented by dynamic data - Shows how to manage free storage - Sometimes needed for maximum efficiency ------------------------------------------ B. array representation ------------------------------------------ ARRAY REPRESENTATION // ACharNode.h typedef int ACharPtr; struct ACharNode { char data; ACharPtr link; }; const ACharPtr NULL_PTR = -1; // client code #include "ACharNode.h" ACharNode heap[100]; ACharPtr head; Abstract diagram: Concrete picture: ------------------------------------------ 1. managing a free store ------------------------------------------ MANAGING A FREE STORE // heap.h #include "ACharNode.h" const int HEAP_SIZE = 10; extern ACharNode heap[HEAP_SIZE]; extern void InitializeHeap(); // POST: initializes the storage in the // heap to be all free extern ACharPtr NewLoc(); // PRE: InitializeHeap has been called // POST: IF space is available // THEN FCTVAL == index of unused spot // ELSE FCTVAL == NULL_PTR extern void Deallocate ( ACharPtr p ); // PRE: InitializeHeap has been called // && p is result of previous call // to NewLoc. // POST: IF p is not NULL_PTR, THEN // p is marked as free ------------------------------------------ ------------------------------------------ MANAGING A FREE STORE (2) // heapHR.C #include "heap.h" #include #include "bool.h" ACharNode heap[HEAP_SIZE]; static Boolean free[HEAP_SIZE]; Picture: ------------------------------------------ ------------------------------------------ OPERATIONS ON FREE STORE // heapHR.C #include "heap.h" #include #include "bool.h" ACharNode heap[HEAP_SIZE]; static Boolean free[HEAP_SIZE]; void InitializeHeap() // MODIFIES: heap // POST: free[0..HEAP_SIZE] == TRUE { for (int i = 0; i < HEAP_SIZE; i++) { free[i] = TRUE; } } ACharPtr NewLoc() // MODIFIES: free // POST: IF space is available in free // THEN FCTVAL == index of unused spot // ELSE FCTVAL == NULL_PTR { } ------------------------------------------ ------------------------------------------ void Deallocate ( ACharPtr p ) // PRE: p is result of previous call // to NewLoc. // MODIFIES: free // POST: IF p is not NULL_PTR, THEN // free[p] == TRUE { } ------------------------------------------ ------------------------------------------ FOR YOU TO DO Implement the following (hint: use NewLoc) // test.C #include #include "ACharNode.h" #include "heap.h" ACharPtr Cons(char c, ACharPtr rest) // MODIFIES: cerr // POST: IF can't allocate // THEN give error and stop program // ELSE return pointer to new AcharNode // initialized with c and rest { } ------------------------------------------ 2. insertion ------------------------------------------ INSERTION // of char x at front of the list head = Cons(x, head); // of char in x after prevPtr heap[prevPtr].link = Cons(x, heap[prevPtr].link); ------------------------------------------ 3. deletion ------------------------------------------ DELETION // of node after prevPtr ACharPtr tempPtr = heap[prevPtr].link; heap[prevPtr].link = heap[tempPtr].link; Deallocate(tempPtr); ------------------------------------------ How would you delete the node pointed to by the list head? C. summary IV. comparison between dynamic and array implementations ------------------------------------------ COMPARING IMPLEMENTATION TECHNIQUES FOR LISTS Array w/ Linked Lists shifting Array Dynamic Fixed size? Space used Insert time O(n) Delete time ------------------------------------------ V. example: implementing list with linked list (HR pp. 365)