Programming and Problem Solving with C++, 2/e

Programming and Problem Solving with C++, 2/e

Chapter 16 Linked Structures Dale/Weems 1 Chapter 16 Topics Meaning of a Linked List Meaning of a Dynamic Linked List Traversal, Insertion and Deletion of Elements in a Dynamic Linked List Specification of a Dynamic Linked Sorted List Insertion and Deletion of Elements in a Dynamic Linked Sorted List 2

What is a List? A list is a varying-length, linear collection of homogeneous elements Linear means that each list element (except the first) has a unique predecessor and each element (except the last) has a unique successor 3 To implement the List ADT The programmer must 1) choose a concrete data representation for the list, and 2) implement the list operations 4

Recall: 4 Basic Kinds of ADT Operations Constructors -- create a new instance (object) of an ADT Transformers -- change the state of one or more of the data values of an instance Observers -- allow client to observe the state of one or more of the data values of an instance without changing them Iterators -- allow client to access the data values in sequence 5 List Operations Transformers

Insert Delete Sort change state Observers IsEmpty IsFull Length IsPresent observe state 6 ADT List Operations Iterator

Reset GetNextItem Iteration Pair Reset prepares for the iteration GetNextItem returns the next item in sequence No transformer can be called between calls to GetNextItem (Why?) 7 Array-based class List SelSort IsEmpty IsFull Length Insert Delete

IsPresent Reset Private data: length data 0] [1] [2] [ [MAX_LENGTH-1] currentPos GetNexItem 8 // Specification file array-based list (list.h) const int MAX_LENGTH = 50; typedef int ItemType;

class List { public: // Declares a class data type // Public member functions List(); // constructor bool IsEmpty () const; bool IsFull () const; int Length () const; // Returns length of list void Insert (ItemType item); void Delete (ItemType item); bool IsPresent(ItemType item) const; void SelSort (); void Reset (); ItemType GetNextItem (); private: // Private data members int length; // Number of values currently stored ItemType data[MAX_LENGTH];

int CurrentPos; // Used in iteration }; 99 Implementation Structures Use a built-in array stored in contiguous memory locations, implementing operations Insert and Delete by moving list items around in the array, as needed Use a linked list in which items are not necessarily stored in contiguous memory locations A linked list avoids excessive data movement from insertions and deletions 10

Implementation Possibilities for a List ADT List Built-in array Linked list Built-in dynamic data and pointers Built-in array of structs 11 A Linked List A linked list is a list in which the order of the components is determined by an explicit link member in each node

Each node is a struct containing a data member and a link member that gives the location of the next node in the list head X C L 12 Dynamic Linked List A dynamic linked list is one in which the nodes are linked together by pointers and an external pointer (or head pointer) points to the first node in the list

head Ted Irv Lee 13 Nodes can be located anywhere in memory The link member holds the memory address of the next node in the list 3000 head 3000 Ted 5000 5000

Irv 2000 2000 Lee NULL 14 Declarations for a Dynamic Linked List // Type declarations struct NodeType { char info; NodeType* link; } typedef NodeType* NodePtr;

// Variable DECLARATIONS NodePtr head; NodePtr ptr; A 6000 . info . link 1515 Pointer Dereferencing and Member Selection ptr A 6000 . info

. link A 6000 . info . link A 6000 . info . link ptr ptr *ptr

ptr (*ptr).info ptr->info 1616 ptr is a pointer to a node ptr A 6000 . info . link ptr 1717 *ptr is the entire node

pointed to by ptr ptr A 6000 . info . link *ptr 1818 ptr->info is a node member ptr A 6000

. info . link ptr->info (*ptr).info // Equivalent 1919 ptr->link is a node member ptr A 6000 . info . link

ptr->link (*ptr).link // Equivalent 2020 Traversing a Dynamic Linked List ptr 3000 head 3000 Ted 5000 5000 Irv 2000 2000 Lee NULL

// Pre: head points to a dynamic linked list ptr = head; while (ptr != NULL) { cout << ptr->info; // Or, do something else with node *ptr ptr = ptr->link; } 21 Traversing a Dynamic Linked List ptr 3000 3000 head 3000 Ted 5000 5000

Irv 2000 2000 Lee NULL // Pre: head points to a dynamic linked list ptr = head; while (ptr != NULL) { cout << ptr->info; // Or, do something else with node *ptr ptr = ptr->link; } 22 Traversing a Dynamic Linked List ptr 3000

3000 head 3000 Ted 5000 5000 Irv 2000 2000 Lee NULL // Pre: head points to a dynamic linked list ptr = head; while (ptr != NULL) { cout << ptr->info; // Or, do something else with node *ptr ptr = ptr->link; }

23 Traversing a Dynamic Linked List ptr 3000 3000 head 3000 Ted 5000 5000 Irv 2000 2000 Lee NULL // Pre: head points to a dynamic linked list ptr = head;

while (ptr != NULL) { cout << ptr->info; // Or, do something else with node *ptr ptr = ptr->link; } 24 Traversing a Dynamic Linked List ptr 5000 3000 head 3000 Ted 5000 5000 Irv 2000

2000 Lee NULL // Pre: head points to a dynamic linked list ptr = head; while (ptr != NULL) { cout << ptr->info; // Or, do something else with node *ptr ptr = ptr->link; } 25 Traversing a Dynamic Linked List ptr 5000 3000

head 3000 Ted 5000 5000 Irv 2000 2000 Lee NULL // Pre: head points to a dynamic linked list ptr = head; while (ptr != NULL) { cout << ptr->info; // Or, do something else with node *ptr ptr = ptr->link; } 26

Traversing a Dynamic Linked List ptr 5000 3000 head 3000 Ted 5000 5000 Irv 2000 2000 Lee NULL // Pre: head points to a dynamic linked list ptr = head; while (ptr != NULL) {

cout << ptr->info; // Or, do something else with node *ptr ptr = ptr->link; } 27 Traversing a Dynamic Linked List ptr 2000 3000 head 3000 Ted 5000 5000 Irv 2000 2000

Lee NULL // Pre: head points to a dynamic linked list ptr = head; while (ptr != NULL) { cout << ptr->info; // Or, do something else with node *ptr ptr = ptr->link; } 28 Traversing a Dynamic Linked List ptr 2000 3000 head 3000

Ted 5000 5000 Irv 2000 2000 Lee NULL // Pre: head points to a dynamic linked list ptr = head; while (ptr != NULL) { cout << ptr->info; // Or, do something else with node *ptr ptr = ptr->link; } 29 Traversing a Dynamic Linked List

ptr 2000 3000 head 3000 Ted 5000 5000 Irv 2000 2000 Lee NULL // Pre: head points to a dynamic linked list ptr = head; while (ptr != NULL) { cout << ptr->info; // Or, do something else with node *ptr

ptr = ptr->link; } 30 Traversing a Dynamic Linked List ptr NULL 3000 head 3000 Ted 5000 5000 Irv 2000 2000 Lee NULL

// Pre: head points to a dynamic linked list ptr = head; while (ptr != NULL) { cout << ptr->info; // Or, do something else with node *ptr ptr = ptr->link; } 31 Traversing a Dynamic Linked List ptr NULL 3000 head 3000 Ted 5000

5000 Irv 2000 2000 Lee NULL // Pre: head points to a dynamic linked list ptr = head; while (ptr != NULL) { cout << ptr->info; // Or, do something else with node *ptr ptr = ptr->link; } 32 Using Operator new Recall If memory is available in the free store (or heap), operator new allocates the requested object and

returns a pointer to the memory allocated The dynamically allocated object exists until the delete operator destroys it 33 item B Inserting a Node at the Front of a List char item = B; NodePtr location; location = new NodeType; location->info = item; location->link = head; head = location;

head X C L 34 item B Inserting a Node at the Front of a List char item = B; NodePtr location; location = new NodeType; location->info = item; location->link = head; head = location;

head location X C L 35 item B Inserting a Node at the Front of a List char item = B; NodePtr location; location = new NodeType;

location->info = item; location->link = head; head = location; head location X C L 36 item B Inserting a Node at the Front of a List

char item = B; NodePtr location; location = new NodeType; location->info = item; location->link = head; head = location; head X location B C L 37 item

B Inserting a Node at the Front of a List char item = B; NodePtr location; location = new NodeType; location->info = item; location->link = head; head = location; head X location B C

L 38 item B Inserting a Node at the Front of a List char item = B; NodePtr location; location = new NodeType; location->info = item; location->link = head; head = location; head X

location B C L 39 Using Operator delete When you use the operator delete The object currently pointed to by the pointer is deallocated and the pointer is considered undefined The objects memory is returned to the free store 40 Deleting the First Node from the List

item NodePtr tempPtr; item = head->info; tempPtr = head; head = head->link; delete tempPtr; head tempPtr B X C L

41 item B Deleting the First Node from the List NodeType * tempPtr; item = head->info; tempPtr = head; head = head->link; delete tempPtr; head tempPtr

B X C L 42 item B Deleting the First Node from the List NodeType * tempPtr; item = head->info; tempPtr = head;

head = head->link; delete tempPtr; head tempPtr B X C L 43 item B Deleting the First Node from the List

NodeType * tempPtr; item = head->info; tempPtr = head; head = head->link; delete tempPtr; head tempPtr B X C L 44

item B Deleting the First Node from the List NodeType * tempPtr; item = head->info; tempPtr = head; head = head->link; delete tempPtr; head tempPtr X

C L 45 What is a Sorted List? A sorted list is a variable-length, linear collection of homogeneous elements, ordered according to the value of one or more data members The transformer operations must maintain the ordering In addition to Insert and Delete, lets add two new operations to our list InsertAsFirst and RemoveFirst 46 ADT HybridList Operations Transformers InsertAsFirst Insert RemoveFirst

Delete change state Same observers and iterators as ADT List Since we have two insertion and two deletion operations, lets call this a Hybrid List 47 struct NodeType // Specification file sorted list (slist2.h) typedef int ItemType; struct NodeType { ItemType item; NodeType* link; }; typedef NodeType* // Type of each component is

// a simple type or a string // Pointer to persons name // Link to next node in list NodePtr; 4848 // Specification file class HybridList { public: hybrid sorted list(slist2.h) bool IsEmpty () const; void InsertAsFirst (/* in */ void Insert (/* in */ ItemType ItemType

void RemoveFirst(/* out */ item); item); ItemType& item); void Delete (/* in */ ItemType item); void Print () const; HybridList (); // Constructor ~HybridList (); // Destructor HybridList (const HybridList& otherList); // Copy-constructor private: NodeType* }; head; 4949

class HybridList HybridList ~HybridList Private data: IsEmpty Print head C L X InsertASFirst Insert RemoveFirst Delete 50

Insert Algorithm What will be the algorithm to Insert an item into its proper place in a sorted linked list? That is, for a linked list whose elements are maintained in ascending order? 51 Insert algorithm for HybridList Find proper position for the new element in the sorted list using two pointers prevPtr and currPtr, where prevPtr trails behind currPtr

Obtain a new node and place item in it Insert the new node by adjusting pointers 52 Implementing HybridList Member Function Insert // Dynamic linked list implementation (slist2.cpp) void HybridList::Insert (/* in */ ItemType item) // PRE: // item is assigned && components in ascending order // POST: // item is in List && components in ascending order { . .

. } 53 Inserting S into a List prevPtr currPtr Private data: head C L X 54 Finding Proper Position for S prevPtr

NULL currPtr Private data: head C L X 55 Finding Proper Position for S prevPtr currPtr Private data: head

C L X 56 Finding Proper Position for S prevPtr currPtr Private data: head C L X 57

Inserting S into Proper Position prevPtr currPtr Private data: head C L X S 58 // Implementation file for HybridList (slist.cpp) HybridList::HybridList () // Constructor // Post: head == NULL { head = NULL;

} HybridList::~HybridList () // Destructor // Post: All linked nodes deallocated { ItemType temp; // Keep deleting top node while (!IsEmpty) RemoveFirst (temp); } 5959 void HybridList::Insert(/* in */ ItemType item) // Pre: item is assigned && components in ascending order // Post: new node containing item is in its proper place // && components in ascending order

{ NodePtr currPtr; NodePtr prevPtr; NodePtr location; location = new NodeType; newNodePtr->link = item; prevPtr = NULL; currPtr = head; while (currPtr != NULL && item > currPtr->info ) { prevPtr = currPtr; // Advance both pointers currPtr = currPtr->link; } location->link = currPtr;// Insert new node here if (prevPtr == NULL) head = location; else

prevPtr->link = location; } 6060 void HybridList::InsertAsFirst(/* in */ ItemType item) // Pre: item is assigned && components in ascending order // Post: New node containing item is the first item in the list // && components in ascending order { NodePtr newNodePtr = new NodeType; newNodePtr -> component = item; newNodePtr -> link = head; head = newNodePtr; } Void HybridList::Print() const

// Post: All values within nodes have been printed { NodePtr currPtr = head; // Loop control pointer while (currPtr != NULL) { cout << currPtr->component << endl; currPtr = currPtr->link; } } 6161 void HybridList::RemoveFirst ( /* out */ ItemType& item) // Pre: list is not empty && components in ascending order // Post: item == element of first list node @ entry // && node containing item is no longer in list // && list components in ascending order { NodePtr tempPtr = head; // Obtain item and advance head

item = head->info ; head = head->link; delete tempPtr; } 6262 void HybridList::Delete (/* in */ ItemType item) // Pre: list is not empty && components in ascending order // && item == component member of some list node // Post: item == element of first list node @ entry // && node containing first occurrence of item no longer // in list && components in ascending order { NodePtr delPtr; NodePtr currPtr; // Is item in first node? if (item == head->info)

{ // If so, delete first node delPtr = head; head = head->link; } else {// Search for item in rest of list { currPtr = head; while (currPtr->link->info != item) currPtr = currPtr->link; delPtr = currPtr->link; currPtr->link = currPtr->link->link; } delete delPtr; 6363 } Copy Constructor Most difficult algorithm so far If the original is empty, the copy is empty Otherwise, make a copy of the head with pointer to it Loop through original, copying each

node and adding it to the copy until you reach the end See Chapter 18 for an easy, elegant solution 64 A Month of Day Lists Insert Figure 16-7 on page 879 65

Recently Viewed Presentations

  • Graphic Design - Uplift Education

    Graphic Design - Uplift Education

    Color Theory Project. Create 2 images: color wheel and monochromatic . Can be abstract . Illustrate a narrative . No white space. 2 wks to complete . All orginal artwork . Examples. Example. Exit Ticket . What progress have you...
  • Strategies for increasing data quality

    Strategies for increasing data quality

    The average ability to access reports score increased from 3.5 during call one in October to 4.2 during call two in January. Challenges/lessons learned: Identifying a learning progression for data skills. There can be multiple people on a call who...
  • Electromagnetic Radiation - Oneonta

    Electromagnetic Radiation - Oneonta

    * * * * * * * * * * * * * * Shells, Subshells and Orbitals Which subshell does not exist? 5s 2p 2d 4f 15s NODES Spherical Nodes Quantum Numbers and Numbers of Orbitals * * *...
  • Project Mayibuye - Missouri Library Association

    Project Mayibuye - Missouri Library Association

    Impact of this Project. Project Mayibuye will make historical papers, photographs, sound and oral history, film and video, as well as numerous art and artifact collections more readily available, to help the world understand the struggle for freedom from apartheid...
  • Tally&#x27;s Blood - WordPress.com

    Tally's Blood - WordPress.com

    Tally's Blood Ann Marie Di Mambro - Franco and Bridget. Although Franco does enjoy his status as a heroic figure, he does seem to be genuinely in love with Bridget, prepared to risk his father's wrath and boasting about her...
  • Main Idea and Supporting Details - Jefferson County Public ...

    Main Idea and Supporting Details - Jefferson County Public ...

    Main Idea and Supporting Details Third Grade SPI 0301.6.2 Identify the stated main idea in a selection. SPI 0301.6.4 Identify main idea and supporting details in a text. Main Idea Every story or paragraph has a main idea. The main...
  • Risk Management - Sandvik

    Risk Management - Sandvik

    Sandvik Australia Pty Ltd David Stone Corporate Risk & Compliance Dept [email protected] 0400 951130
  • Real Options in Equity Partnerships

    Real Options in Equity Partnerships

    Extend a developing literature using option theory to diagnose the motives for incrementally committing to strategies through sequential investment processes. ... uncertainty of parent value. T: length of time the buyout decision may be deferred . r: risk-free rate of...