Chapter 4 Linked Lists Data Abstraction Problem Solving with C Fifth Edition by Frank M Carrano Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 Preliminaries Options for implementing an ADT List Array has a fixed size Data must be shifted during insertions and deletions Linked list is able to grow in size as needed Does not require the shifting of items during insertions and deletions Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 2 Preliminaries Figure 4 1 a A linked list of integers b insertion c deletion Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 3 Pointers A pointer contains the location or address in memory of a memory cell Declaration of an integer pointer variable p int p Initially undefined but not NULL Static allocation Figure 4 2 A pointer to an integer Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 4 Pointers The expression p represents the memory cell to which p points To place the address of a variable into a pointer variable you can use The address of operator p x The new operator p new int Dynamic allocation of a memory cell that can contain an integer If the operator new cannot allocate memory it throws the exception std bad alloc in the new header Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 5 Pointers The delete operator returns dynamically allocated memory to the system for reuse and leaves the variable s contents undefined delete p A pointer to a deallocated memory p cell is possible and dangerous p NULL safeguard Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 6 Pointers Figure 4 3 a Declaring pointer variables b pointing to statically allocated memory c assigning a value d allocating memory dynamically e assigning a value Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 7 Pointers Figure 4 3 continued f copying a pointer g allocating memory dynamically and assigning a value h assigning NULL to a pointer variable i deallocating memory Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 8 Dynamic Allocation of Arrays You can use the new operator to allocate an array dynamically int arraySize 50 double anArray new double arraySize An array name is a pointer to the array s first element The size of a dynamically allocated array can be increased double oldArray anArray anArray new double 2 arraySize Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 9 Pointer Based Linked Lists A node in a linked list is usually a struct struct Node int item Node next end Node Figure 4 6 A node The head pointer points to the first node in a linked list Figure 4 7 A head pointer to a list Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 10 Pointer Based Linked Lists If head is NULL the linked list is empty A node is dynamically allocated Node p pointer to node p new Node allocate node Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 11 Pointer Based Linked Lists Executing the statement head new Node before head NULL will result in a lost cell Figure 4 8 A lost cell Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 12 Displaying the Contents of a Linked List Reference a node member with the operator p item A traverse operation visits each node in the linked list A pointer variable cur keeps track of the current node for Node cur head cur NULL cur cur next cout cur item endl Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 13 Displaying the Contents of a Linked List Figure 4 9 The effect of the assignment cur cur next Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 14 Deleting a Specified Node from a Linked List Deleting an interior node prev next cur next Figure 4 10 Deleting a node from a linked list Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 15 Deleting a Specified Node from a Linked List Deleting the first node head head next Figure 4 11 Deleting the first node Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 16 Deleting a Specified Node from a Linked List Return deleted node to system cur next NULL delete cur cur NULL Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 17 Inserting a Node into a Specified Position of a Linked List To insert a node between two nodes newPtr next cur prev next newPtr Figure 4 12 Inserting a new node into a linked list Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 18 Inserting a Node into a Specified Position of a Linked List To insert a node at the beginning of a linked list newPtr next head head newPtr Figure 4 13 Inserting at the beginning of a linked list Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 19 Inserting a Node into a Specified Position of a Linked List Inserting at the end of a linked list is not a special case if cur is NULL newPtr next cur prev next newPtr Figure 4 14 Inserting at the end of a linked list Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 20 Inserting a Node into a Specified Position of a Linked List Finding the point of insertion or deletion for a sorted linked list of objects Node prev cur for prev NULL cur head cur NULL newValue cur item prev cur cur cur next Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 21 A Pointer Based Implementation of the ADT List Figure 4 17 A pointer based implementation of a linked list Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 22 A Pointer Based Implementation of the ADT List Public methods isEmpty getLength insert remove retrieve Private method find Private data members head size Local variables to methods cur prev Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 23 Constructors and Destructors Default constructor initializes size and head A destructor is required for dynamically allocated memory List List while isEmpty remove 1 end destructor Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 24 Constructors and Destructors Copy constructor creates a deep copy Copies size head and