Unformatted text preview:

Chapter 13Pointers and Linked Lists2Overview13.1 Nodes and Linked Lists 13.2 Stacks and Queues313.1Nodes and Linked Lists41012end14headNodes and Linked Lists–A linked list is a list that can grow and shrink while the program is running–A linked list is constructed using pointers–A linked list often consists of structs or classes that contain a pointer variable connecting them to other dynamic variables–A linked list can be visualized as items, drawn as boxes, connected to other items by arrows56Nodes■The boxes in the previous drawing represent the nodes of a linked list–Nodes contain the data item(s) and a pointer that can point to another node of the same type■The pointers point to the entire node, not an individual item that might be in the node■The arrows in the drawing represent pointers7■Nodes are implemented in C++ as structs or classes–Example: A structure to store two data items and a pointer to another node of the same type, along with a type definition might be: struct ListNode { string item; int count; ListNode *link; }; typedef ListNode* ListNodePtr;This circular definition is allowed in C++Implementing Nodes8The head of a List■The box labeled head, in display 13.1, is not a node, but a pointer variable that points to a node■Pointer variable head is declared as: ListNodePtr head;9Accessing Items in a Node■Using the diagram of 13.1, this is one way to change the number in the first node from 10 to 12: (*head).count = 12;–head is a pointer variable so *head is the node that head points to–The parentheses are necessary because the dot operator . has higher precedence than the dereference operator *10The Arrow Operator■The arrow operator -> combines the actions of the dereferencing operator * and the dot operator to specify a member of a struct or object pointed to by a pointer– (*head).count = 12; can be written as head->count = 12;–The arrow operator is more commonly used1112NULL■The defined constant NULL is used as…–An end marker for a linked list■A program can step through a list of nodes by following the pointers, but when it finds a node containing NULL, it knows it has come to the end of the list–The value of a pointer that has nothing to point to■The value of NULL is 0■Any pointer can be assigned the value NULL: double* there = NULL;13To Use NULL■A definition of NULL is found in several libraries, including <iostream> and <cstddef>■A using directive is not needed for NULL14Linked Lists■The diagram in Display 13.2 depicts a linked list■A linked list is a list of nodes in which each node has a member variable that is a pointer that points to the next node in the list–The first node is called the head–The pointer variable head, points to the first node■The pointer named head is not the head of the list…it points to the head of the list–The last node contains a pointer set to NULL15Building a Linked List:The node definition■Let's begin with a simple node definition: struct Node { int data; Node *link; }; typedef Node* NodePtr;16Building a Linked List:Declaring Pointer Variable head■With the node defined and a type definition to make or code easier to understand, we can declare the pointer variable head: NodePtr head;–head is a pointer variable that will point to the head node when the node is created17Building a Linked List:Creating the First Node■To create the first node, the operator new is used to create a new dynamic variable: head = new Node;–Now head points to the first, and only, node in the list18Building a Linked List:Initializing the Node■Now that head points to a node, we need to give values to the member variables of the node: head->data = 3; head->link = NULL;–Since this node is the last node, the link is set to NULL19Function head_insert■It would be better to create a function to insertnodes at the head of a list, such as:– void head_insert(NodePtr& head, int the_number);■The first parameter is a NodePtr parameter that points to the first node in the linked list■The second parameter is the number to store in the list–head_insert will create a new node for the number■The number will be copied to the new node■The new node will be inserted in the list as the new head node20Pseudocode for head_insert■Create a new dynamic variable pointed to by temp_ptr■Place the data in the new node called *temp_ptr■Make temp_ptr's link variable point to the headnode ■Make the head pointer point to temp_ptr2122Translating head_insert to C++■The pseudocode for head_insert can be writtenin C++ using these lines in place of the lines of pseudocode:–NodePtr temp_ptr; //create the temporary pointer temp_ptr = new Node; // create the new node–temp_ptr->data = the_number; //copy the number–temp_ptr->link = head; //new node points to first nodehead = temp_ptr; // head points to new // first node2324An Empty List■A list with nothing in it is called an empty list■An empty linked list has no head node■The head pointer of an empty list is NULL head = NULL;–Any functions written to manipulate a linked listshould check to see if it works on the empty list25■You might be tempted to write head_insert using the head pointer to construct the new node: head = new Node; head->data = the_number;■Now to attach the new node to the list–The node that head used to point to is now lost!Losing Nodes2627Memory Leaks■Nodes that are lost by assigning their pointers a new address are not accessible any longer■The program has no way to refer to the nodesand cannot delete them to return their memoryto the freestore■Programs that lose nodes have a memory leak–Significant memory leaks can cause system crashes28Searching a Linked List■To design a function that will locate a particularnode in a linked list:–We want the function to return a pointer to the node so we can use the data if we find it, else return NULL–The linked list is one argument to the function–The data we wish to find is the other argument–This declaration will work: NodePtr search(NodePtr head, int target);29■Refining our function–We will use a local pointer variable, named here, to move through the list checking for the target■The only way to move around a linked list is to follow pointers–We will start with here


View Full Document

GSU CSC 2311 - ch13

Documents in this Course
ch14

ch14

65 pages

ch06

ch06

110 pages

ch10

ch10

80 pages

Load more
Download ch13
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view ch13 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view ch13 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?