Linked list and bidirectional linked list in Java language

Linked list is an important data structure, which plays a very important role in program design. C language and C + + language use pointers to realize the linked list structure. Because the Java language does not provide pointers, some people think that the linked list cannot be realized in the Java language. In fact, it is not. The Java language is easier to realize the linked list structure than C and C + +. The object reference in the Java language is actually a pointer (the pointers in this article are conceptual, not the data types provided by the language), so we can write such a class to implement the nodes in the linked list. Class node {object data; node next; / / refers to the next node} The data field is defined as the object class because the object class is a generalized superclass. Any class object can assign values to it, which increases the generality of the code. In order to make the linked list accessible, you also need to define a header. The header must contain a pointer to the first node and a pointer to the current node. In order to add nodes at the end of the linked list, you can also add a pointer to the end of the linked list. In addition, you can use a field to represent the size of the linked list. When the caller wants to get the size of the linked list, he does not have to traverse the whole linked list. The following figure is a schematic diagram of this linked list:

For the data structure of linked list, we can use the class list to realize the linked list structure, and use the variables head, tail, length and pointer to realize the header. There are certain skills when storing the pointer of the current node. Pointer does not store the pointer to the current node, but stores the pointer to its forward node. When its value is null, it means that the current node is the first node. So why? This is because after deleting the current node, it is still necessary to ensure that the remaining nodes form a linked list. If the pointer points to the current node, it will bring great difficulties to the operation. So how to get the current node? We define a method cursor (), and the return value is a pointer to the current node. Class list also defines some methods to realize the basic operations on the linked list. By using these basic operations, we can perform various operations on the linked list. For example, the reset () method makes the first node the current node. Insert (object d) method inserts a node before the current node and makes it the current node. The remove () method deletes the current node, returns its contents, and makes its successor node the current node. If the last node is deleted, the first node becomes the current node. The source code of the linked list class list is as follows: import Java io.*; Public class list {/ * use variables to implement the header * / private node head = null; private node tail = null; private node pointer = null; private int length = 0; public void deleteall() / * empty the entire linked list * / {head = null; tail = null; pointer = null; length = 0;} Public void reset() / * linked list reset, Make the first node the current node * / {pointer = null;} public Boolean isempty() / * judge whether the linked list is empty * / {return (length = = 0);} public Boolean isend() / * judge whether the current node is the last node * / {if (length = = 0) throw new java.lang.nullpointerexception() ; 　　else if(Length==1) 　　　return true; 　　else 　　　return(cursor()==Tail); } public object nextnode() / * returns the value of the next node of the current node, And make it the current node * / {if (length = = 1) throw new Java. Util. Nosuchelementexception(); else if (length = = 0) throw new Java. Lang. nullpointerexception(); else {node temp = cursor(); pointer = temp; if (temp! = tail) return (temp. Next. Data) ; 　　　else 　　　　throw new java. util. NoSuchElementException(); }} public object currentnode() / * returns the value of the current node * / {node temp = cursor(); return temp. Data;} public void insert (object d) / * inserts a node in front of the current node, And make it the current node * / {node e = new node (d); if (length = = 0) {tail = E; head = E;} else {node temp = cursor(); e.next = temp; if (pointer = = null) head = E; else pointer. Next = E;} length + +; } public int size() / * returns the size of the linked list * / {return (length);} public object remove() / * moves the current node out of the linked list, and the next node becomes the current node. If the moved node is the last node, Then the first node becomes the current node * / {object temp; if (length = = 0) throw new Java. Util. Nosuchelementexception(); else if (length = = 1) {temp = head. Data; deleteall();} else {node cur = cursor(); temp = cur. Data; if (cur = = head) 　　　　Head=cur. next; 　　　else if(cur==Tail) 　　　{ 　　　　Pointer.next=null; 　　　　Tail=Pointer; 　　　　reset(); 　　　} 　　　else 　　　　Pointer. next=cur. next; 　　　　Length－－; 　　} 　　return temp; } private node cursor() / * returns the pointer of the current node * / {if (head = = null) throw new Java. Lang. nullpointerexception(); else if (pointer = = null) return head; else return pointer. Next;} public static void main (string [] args) / * simple application example of linked list * / { 　　List a=new List (); 　　for(int i=1;i<=10;i＋＋) 　　　a.insert(new Integer(i)); 　　　System.out.println(a.currentNode()); 　　　while(!a.isEnd()) 　　　　System.out.println(a.nextNode()); 　　　　a.reset(); 　　　　while(!a.isEnd()) 　　　　{ 　　　　　a.remove(); 　　　　} 　　　　a.remove(); 　　　　a.reset(); 　　　　if(a.isEmpty()) 　　　　　System. out. println("There is no Node in List \n"); 　　　　　system. in. println("You can press return to quit\n"); Try {system. In. Read(); / / make sure that the user can see the program running result} catch (IOException E) {}}} class node / * node definition constituting the linked list * / {object data; node next; node (object d) {data = D; next = null;}} readers can also define new methods to operate the linked list according to their actual needs. The bidirectional linked list can be implemented in a similar way, but the node class adds a pointer to the forward node. You can use this code to implement: class node {object data; node next; node previous; node (object d) {data = D; next = null; previous = null;}} of course, the implementation of the basic operations of the two-way linked list is slightly different. The implementation methods of linked list and bidirectional linked list can also be used in the implementation of stack and queue. There is no more writing here. Interested readers can change the code of list class slightly.