data.docx

# Linked List ## Course Objectives: * Identify linked list * Use Insertion and Deletion in linked list * Traversing linked list ## Linked lists A linked list is a collection of components called nodes. Every node (except the last node) contains the address of the next node. Thus, every node in a linked list has two components: one to store the relevant information (that is, data) and one to store the address, called the link, of the next node in the list. The address of the first node in the list is stored in a separate location called the head or first node. ### Linked List Diagram: ![[Image of a linked list with arrows pointing from one node to the next]] *Linked List: A list of items, called nodes, in which the order of the nodes is determined by the address, called the link, stored in each node.* The arrow in each node indicates that the address of the node to which it is pointing is stored in that node. The down arrow in the last node indicates that this link field is NULL. For a better understanding of this notation, suppose that the first node is at memory location 1200, and the second node is at memory location 1575. ### Memory locations Diagram: ![[Image of a linked list diagram with memory locations]] The value of the head is 1200, the data part of the first node is 45, and the link component of the first node contains 1575, the address of the second node. If no confusion arises, then we will use the arrow notation whenever we draw the figure of a linked list. ## Linked Lists: #### Node Structure Definition: ```c++ struct nodeType { int info; nodeType *link; }; ``` Because each node of a linked list has two components, we need to declare each node as a class or struct. The data type of each node depends on the specific application (that is, what kind of data is being processed). However, the link component of each node is a pointer. The data type of this pointer variable is the node type itself. For the previous linked list, the definition of the node is as follows. (Suppose that the data type is int.) ##### Variable Declaration: ```c++ nodeType *head; ``` ## Linked Lists: Some properties This linked list has four nodes. The address of the first node is stored in the pointer head. Each node has two components: info, to store the info, and link, to store the address of the next node. For simplicity, we assume that info is of type int. ### Linked List Properties Diagram: ![[Image of a linked list diagram showing data and link components]] *head* | *Value* | *Explanation* ------- | -------- | -------- head | 2000 | head->info | 17 | Because head is 2000 and the info of the node at location 2000 is 17 head->link | 2800 | head->link->info | 92 | Because head->link is 2800 and the info of the node at location 2800 is 92 Suppose that current is a pointer of the same type as the pointer head. Then, the statement: *current = head;* copies the value of head into *current*. ### Linked List Properties Diagram with current pointer: ![[Image of a linked list diagram showing data and link components with a current pointer]] *current* | *Value* ------- | -------- current | 2000 current->info | 17 current->link | 2800 current->link->info | 92 Now consider the statement: *current = current->link;* This statement copies the value of *current->link*, which is 2800, into *current*. Therefore, after this statement executes, *current* points to the second node in the list. (When working with linked lists, we typically use these types of statements to advance a pointer to the next node in the list.) ### Linked List Properties Diagram with current pointer pointing to the second node: ![[Image of a linked list diagram showing data and link components with a current pointer pointing to the second node]] *current* | *Value* ------- | -------- current->info | 92 current->link | 1500 current->link->info | 63 ## Traversing a Linked List The basic operations of a linked list are as follows: search the list to determine whether a particular item is in the list, insert an item in the list, and delete an item from the list. These operations require the list to be traversed. That is, given a pointer to the first node of the list, we must step through the nodes of the list. Suppose that the pointer *head* points to the first node in the list, and the link of the last node is NULL. We cannot use the pointer *head* to traverse the list because if we use *head* to traverse the list, we would lose the nodes of the list. This problem occurs because the links are in only one direction. The pointer *head* contains the address of the first node, the first node contains the address of the second node, the second node contains the address of the third node, and so on. If we move *head* to the second node, the first node is lost (unless we save a pointer to this node). If we keep advancing *head* to the next node, we will lose all of the nodes of the list (unless we save a pointer to each node before advancing *head*, which is impractical because it would require additional computer time and memory space to maintain the list). ## Traversing a Linked List: Therefore, we always want *head* to point to the first node. It now follows that we must traverse the list using another pointer of the same type. Suppose that *current* is a pointer of the same type as *head*. The following code traverses the list: ```c++ current = head; while (current != NULL) {//Process the current node current = current->link; } ``` For example, suppose that *head* points to a linked list of numbers. The following code outputs the data stored in each node: ```c++ current = head; while (current != NULL) { cout << current->info << " "; current = current->link; } ``` ## Insertion Suppose that *p* points to the node with info 65, and a new node with info 50 is to be created and inserted after *p*. Consider the following statements: ```c++ newNode = new nodeType; // create newNode newNode->info = 50; // store 50 in the new node newNode->link = p->link; p->link = newNode; ``` ### Insertion Diagram: ![[Image of a linked list diagram with code snippets showing the steps in inserting a new node]] Note that the sequence of statements to insert the node is very important because to insert *newNode* in the list, we use only one pointer, *p*, to adjust the links of the node of the linked list. Suppose that we reverse the sequence of the statements and execute the statements in the following order: ```c++ p->link = newNode; newNode->link = p->link; ``` Figure 18-8 shows the resulting list after these statements execute. ### Insertion Diagram with incorrect code sequence: ![[Image of a linked list diagram with incorrect code sequence]] From Figure 18-8, it is clear that *newNode* points back to itself and the remainder of the list is lost. Using two pointers, we can simplify the insertion code somewhat. Suppose *q* points to the node with info 34 (see Figure 18-9). ### Insertion Diagram with two pointers: ![[Image of a linked list diagram with two pointers]] The following statements insert *newNode* between *p* and *q*: ```c++ newNode->link = q; p->link = newNode; ``` The order in which these statements execute does not matter. To illustrate this, suppose that we execute the statements in the following order: ```c++ p->link = newNode; newNode->link = q; ``` Table 18-2 shows the effect of these statements. ### Insertion Diagram with two pointers and changing code sequence: ![[Image of a linked list diagram with two pointers and changing code sequence]] ## Deletion ### Deletion Diagram: ![[Image of a linked list diagram illustrating the node to be deleted]] Suppose that the node with info 34 is to be deleted from the list. The following statement removes the node from the list. ```c++ p->link = p->link->link; ``` ### Deletion Diagram with p->link = p->link->link: ![[Image of a linked list diagram with p->link = p->link->link]] From Figure 18-11, it is clear that the node with info 34 is removed from the list. However, the memory is still occupied by this node, and this memory is inaccessible; that is, this node is dangling. To deallocate the memory, we need a pointer to this node. The following statements delete the node from the list and deallocate the memory occupied by this node.

Document Details

Related

Full Transcript

Upgrade to continue