Engineering.purdue.edu



This is the fifth and the last lecture about linked list.Sometimes, we want to visit every node in a linked list without changing the linked list. For example, we want to print the values stored in the linked list. This is an example of a print function. The function that visits every node is called traversing the linked list.The function takes only one argument as a pointer to the first node of the linked list.As usual, we check whether H is NULL first. If it is not NULL, we can print the value.Then, H moves to the next node. It is correct that we will lose the linked inside this function because H has moved. However, this is not a real problem because the caller of this function should still keep the first node of the linked list.The function visits every node until reaching the end of the linked list.Let’s change the subject and review the insert function. When we talked about the insert function, the newly added node will be the very first node. The reason is this line. It puts the newly inserted node before the previously first node of the linked list. This creates a stack because the first inserted node will be at the end of the linked list.What should we do if we want to insert the new node at the end of the linked list? When we do that, we are creating a queue. It is a queue because the first inserted node will be at the beginning of the linked list. The last inserted node will be at the end of the linked list.The insert function is very similar. First, the function calls the node construct function to create a new node.If the linked list is currently empty, then the newly created node is the first and only node. If the linked list is not empty, we need to find the last node of the linked list. We use another pointer called Q and it is initialized to point to the first node of the linked list.It is accomplished by this while block.This while block moves Q to the last node. As long as Q’s next is not NULL, Q moves to the next node.How does this work?Q is initialized to point to the first node.The program checks whether Q’s next is NULL. If it is not NULL, Q moves to the next.Q moves to the next again.When Q’s next is NULL, Q is the last node.This line puts P as Q’s next. This line changes the link as shown in the slide.The function returns H because it is the first node of the linked list.The next slide is a question for you. How can you write the insert function so that the numbers are sorted in the ascending order? Suppose the linked list currently stores numbers 23, 38, 65, and 74. The newly added node has value 49. How can you find the node that should be before 49 and insert 49 here.Please make sure your program can handle three different cases: First, the inserted number is smaller than all the existing numbers in the linked list. Second, the inserted number is between two numbers already in the linked list. Third, the inserted number is greater than all the existing numbers in the linked list.Next, we will cover a new topic called doubly linked list.The linked list we talked about so far has only one link per node. The link points to the next node. In a doubly linked list, each node has two links: next and previous. The nodes are organized in this way. The next links go in one direction. The previous links go in the opposite direction.How does a doubly linked list work? Consider two nodes pointed by P and Q . .If Q points to P’s next node, then P. arrow next stores the address that is also stored in Q. .At the same time, P points to the same node as Q’s previous. That means the address stored in P’s value is the same address stored in Q. arrow previous.A doubly linked list usually maintain two pointers: head and tail. They point to the two end of the linked list. NULL is used at both ends to indicate there is no next node or previous node at the end.What is the advantage of doubly linked list? It is can forward or backward easily. When a node has only one point, it can go in only one direction. Since a doubly linked list can go backward, when inserting a new node, we do not have to keep two pointers for the purpose of tracking the node before the insertion.Using the tail pointer, inserting a node at the end is much faster because it is not necessary to go over the entire linked list to find the last node in the linked list.However, a doubly linked list has no advantage when inserting a node at the middle. From the head or the tail, we still need to go through many nodes in order to find the middle of the linked list.Even though each node has two pointers, a doubly linked list is still a one-dimensional data structure. It does not have the advantage as a binary tree that can divide into left part and right part. ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download