[ Data Structures with Java ] Section 10.1 : Single Linked Lists (單向鏈結)

Preface : 
A singly linked list is a linear structure. Each element is a node that consists of a value and a reference to the next node in the sequence. A node with its two fields can reside anywhere in memory. We say that a linked structure uses noncontiguous memory to store the elements. Below figure is a view of a singly linked list. An arrow emanating from a node represents a reference to the next(successor) node. The list maintains a reference variable, front, that identifies that first element in the sequence. The list ends when the link (reference) is null : 
 

Creating a Linked List : 
Elements in a linked list are nodes. These are objects that have two instance variables. The first variable, nodeValue, is of generic type T. The second variable is a Node reference next; it provides a link to the next node. 
Let us look at the declaration of the Node class. Be aware that linked lists are implementation structures and so Node objects are rarely visible in the public interface of a data structure. As a result, we declare the instance variable in the Node class public. This greatly simplifies the writing of linked-list methods. The Node class is a self-referencing structure, in which the instance variable, next, refers to an object of its own type. The class has two constructors that combine with the operator new to create a node : 

- Node class :

view plaincopy to clipboardprint?

1. public class Node {  
2.     public T nodeValue;  
3.     public Node next;  
4.       
5.     public Node(){  
6.         nodeValue = null;  
7.         next = null;  
8.     }  
9.       
10.     public Node(T item) {  
11.         nodeValue = item;  
12.         next = null;  
13.     }  
14. }  

In order to have a linked list, we need to define a reference variable that identifies that first node in the list. Appropriately, we call the Node reference front. The role of front is critical in a linked list. It marks the first node in the list, you can use its reference next to proceed to the second node, third node and so on. In a real sense, front defines the list. Let us create a two-element linked list in which the nodes have string values "red" and "green". The variable frontreferences the node "red" : 

view plaincopy to clipboardprint?

1. Node front, p, q;  
2. p = new Node("red");  
3. q = new Node("green");  
4. p.next = q;  
5. front = p;  

An empty linked list is a list without any nodes. In this case, front doesn't reference a first node; rather it has the value null. The condition "front==null" tests for an empty list. Below figure shows actions of upper code : 
 

General Insert and Delete Operation : 
In a list, we are familiar with the concept of inserting a new node at a position or deleting an existing node at a position. The algorithm point out a problem that is inherit in a singly linked list. Because a node can reference only the next (successor) element, updates must occur after a node. Let use look at the algorithm that adds a new node at position curr. We want to insert the new element in such a way that it slides the specified node and all subsequent nodes to the right by one position. The effect is to add the new node before the specified node. As the below figure illustrates, the algorithm must have access to the predecessor node prev because an update occurs with the next field of prev : 
 
From the figure upper, we can transfer the concept into code below : 

view plaincopy to clipboardprint?

1. Node curr, prev, newNode;  
2. newNode = new Node(value);  
3. newNode.next = curr;  
4. prev.next = newNode  

Deleting the node at position curr also requires access to the predecessor node prev. The algorithm involves updating the link in the predecessor node. Set the value of prev to reference the successor of curr. This has the effect of disconnecting curr from the list. 

Removing a Target Node : 
A programmer often wants to access of updates nodes in a linked list according to their value rather than their position in the list. Let us design an algorithm that removes the first occurrence of a node having a specified value. This provides an opportunity to draw on many of the concepts we developed in the previous sections. We will implement the algorithm with the static method remove(item). 
Removing a node with a specified target value begins with a scan of the list to identify the location of the target node. Simply having a reference to the target node is not sufficient because we must also have a reference to the predecessor node. The scan must use a pair of references that move in tandem down the list. One reference identifies the current node in the scan, the other the previous node. Below figure illustrates the relative location for the tandem references curr and prev : 
 

The generic method remove() has a parameter list that includes a reference to the front of the list and the target value. The method returns the value offront, which may have been updated if the deletion occurs at the first node in the list. We include remove() as a static method in the Node class : 

- 函數 remove() 代碼 :

view plaincopy to clipboardprint?

1. public static  Node remove(Node front, T target) {  
2.     Node curr = front;  
3.     Node prev = null;  
4.     while(curr!=null) {  
5.         if(curr.nodeValue.equals(target)) {  
6.             if(prev==null) { // deletion is the first element  
7.                 front = curr.next;  
8.                 break;  
9.             } else {  
10.                 prev.next = curr.next;  
11.                 break;  
12.             }  
13.         }  
14.         prev = curr;  
15.         curr = curr.next;  
16.     }  
17.     return front;  
18. }  

Program 10.1 : 
Let us look a program that uses most of the singly linked list concepts from this section. A prompt asks the user to enter the number of elements in the list. Building the list involves inserting at the front random values in the range from 0 to 99. A call to toString(front) displays the original list. The program then sets in motion an algorithm to output elements in descending order of their value. The key feature is the static method getMaxNode(), which scans the list and returns a reference to the node with the maximum value. The value at this node is output and then used with remove() to delete the value from the list. Iterations that output and then remove the maximum value continue until the list is empty : 

- 函式 getMaxNode() 代碼 :

view plaincopy to clipboardprint?

1. public static extends Comparablesuper T>> Node getMaxNode(Node front) {  
2.     Node target = front, pNode = front.next;  
3.     while(pNode!=null) {  
4.         if(target.nodeValue.compareTo(pNode.nodeValue)>0) {  
5.             target = pNode;  
6.         }  
7.         pNode = pNode.next;  
8.     }  
9.     return target;  
10. }  

- 呼叫Main程式代碼 :

view plaincopy to clipboardprint?

1. public static void main(String args[]) {  
2.     Node front = null, newNode, p=null;  
3.     Random rnd = new Random();  
4.     Scanner keyIn = new Scanner(System.in);  
5.     int listCount;  
6.     System.out.println("Enter the size of the list: ");  
7.     listCount = keyIn.nextInt();  
8.     for(int i=0; i
9.         newNode = new Node(rnd.nextInt(100));  
10.         if(i==0) {  
11.             front = newNode;  
12.             p = newNode;  
13.         } else {  
14.             p.next = newNode;  
15.             p = newNode;  
16.         }  
17.     }  
18.     System.out.println("Original list: ");  
19.     System.out.println(Nodes.toString(front));  
20.       
21.     System.out.println("Ordered list: ");  
22.     while(front!=null) {  
23.         p = Nodes.getMaxNode(front);  
24.         System.out.print(p.nodeValue+" ");  
25.         front = Nodes.remove(front, p.nodeValue);  
26.     }  
27.     System.out.println();  
28. }  

Output :
Enter the size of the list: 10 < 輸入 number of elements >
Original list:
[10, 33, 9, 41, 63, 15, 61, 59, 95, 72]
Ordered list:
9 10 15 33 41 59 61 63 72 95

Supplement : 
* [ 資料結構 小學堂 ] 鏈結串列 : 單向鏈結串列