OO C Class 7 Objectives Differentiate between a static data structure and a dynamic data structure Create a dynamic data structure class using a linked list Describe how nodes are inserted and remove from a linked list 2 What is a linked list It is a collection of items created dynamically at run time Each item node is connected through a pointer Linked lists are differentiated from an array which is created at compile time and is accessed via a subscript The elements in a linked list are accessed via a pointer A linked list node consists of a data portion and at least one pointer 3 Data At run time 25 nextPtr Null 1 A node consisting of a data portion and a pointer is created 2 It s address is placed in a pointer firstptr 3 The programmer can then place data in the data portion of the node 4 The programmer should then set nextPtr to Null or connect it to another node if there is one 4 1 Another node consisting of a data portion and a pointer is created Existing node Data 25 nextPtr Null 2 It s address is placed in a pointer currentPtr firstptr 45 3 The programmer can then place data in the data portion of the node 5 1 The two nodes need to be connected Data 25 2 Should the node with the 45 be placed before or after the node with the 25 nextPtr Null currentPtr firstptr 45 6 1 Placing it to the right would be processing the linked list as a queue 2 To the left would be a stack Data 25 nextPtr Null currentPtr 45 firstptr 7 1 To add the new node to the end of the linked list means connecting the pointer in the node with the 25 to the beginning of the node with the 45 and setting the node with the 45 pointer to Null Data 25 nextPtr Null currentPtr 45 firstptr 8 1 To add the new node to the end of the linked list means connecting the pointer in the node with the 25 to the beginning of the node with the 45 and setting the node with the 45 pointer to Null Data 25 nextPtr currentPtr 45 Null firstptr 9 1 To add the new node to the beginning of the linked list means setting the 45 node s nextPtr to point to the 25 node and then setting firstptr the value of currentPtr so that it points to the 45 node and then Data 25 nextPtr Null currentPtr 45 firstptr 10 Creating a class containing a node structure and methods for processing a linked list 11 Specification file for the List class ifndef NUMBERLIST H define NUMBERLIST H typedef int ListItemType class List private struct ListNode ListItemType value struct ListNode next ListNode head List head pointer int size 12 ListNode find int index const public List Constructor List const List head NULL size 0 List Destructor void appendNode ListItemType void insert int const ListItemType void remove int index void retrieve int const ListItemType bool isEmpty const int getLength const 13 List List const List aList size aList size if aList head NULL head NULL original list is empty else copy first node head new ListNode head item aList head item copy rest of list ListNode newPtr head new list pointer newPtr points to last node in new list 14 origPtr points to nodes in original list for ListNode origPtr aList head next origPtr NULL origPtr origPtr next newPtr next new ListNode newPtr newPtr next newPtr item origPtr item end for newPtr next NULL end if end copy constructor 15 List List while isEmpty remove 1 end destructor bool List isEmpty const return size 0 end isEmpty int List getLength const return size end getLength 16 List ListNode List find int index const if index 1 index getLength return NULL else count from the beginning of the list ListNode cur head for int skip 1 skip index skip cur cur next return cur end if end find 17 void List retrieve int index ListItemType dataItem const if index 1 index getLength cout ListIndexOutOfRangeException retrieve index out of range else get pointer to node then data in node ListNode cur find index dataItem cur item end if end 18 void List insert int index const ListItemType newItem int newLength getLength 1 if index 1 index newLength cout ListIndexOutOfRangeException insert index out of range else ListNode newPtr new ListNode size newLength newPtr item newItem attach new node to list if index 1 insert new node at beginning of list newPtr next head head newPtr 19 else ListNode prev find index 1 insert new node after node to which prev points newPtr next prev next prev next newPtr end if end if end insert 20 void List remove int index ListNode cur if index 1 index getLength cout ListIndexOutOfRangeException remove index out of range else size if index 1 delete the first node from the list cur head save pointer to node head head next 21 else ListNode prev find index 1 delete the node after the node to which prev points cur prev next save pointer to node prev next cur next end if return node to system cur next NULL delete cur cur NULL end if end remove 22 Saves a linked list s data in a text file of integers head points to the linked list fileName is a string that names an external text file to be created ofstream outFile fileName traverse the list to the end writing each item for Node cur head cur NULL cur cur next outFile cur item endl outFile close Assertion The text file contains the linked list s data in its original order 23 Templating a class for a linked list 24 Specification file for the LinkedList class ifndef LINKEDLIST H define LINKEDLIST H template class T class LinkedList private Declare a structure for the list struct ListNode T value struct ListNode next 25 public LinkedList Constructor head NULL LinkedList Destructor void appendNode T void insertNode T void deleteNode T void displayList endif 26 Implementation file for the LinkedList class include iostream For cout and NULL include LinkedList h using namespace std template class T void LinkedList T appendNode T num ListNode newNode nodePtr Allocate a new node store num newNode new ListNode newNode value num newNode next NULL 27 If there are no nodes in the list make newNode the first node if head head newNode else Otherwise insert newNode at end Initialize nodePtr to head of list nodePtr head Find the last node in the list while nodePtr next nodePtr nodePtr next Insert newNode as the last node nodePtr next newNode 28 template class T void LinkedList T displayList ListNode nodePtr nodePtr head while nodePtr cout nodePtr value endl nodePtr nodePtr next 29 template class T void LinkedList T insertNode T num ListNode newNode nodePtr previousNode NULL Allocate a new node store num newNode new ListNode newNode value num If there are no nodes in the list