Linked list is a kind of Physics Storage unit
Upper discontinuous, non sequential storage structure ，data elements The logical order of is through the Pointer
Link order. The list consists of a series of nodes (each element in the list is called a node), which can be generated dynamically at runtime. Each node consists of two parts: one is storage data elements The other is to store the address of the next node Pointer
Domain. Compared to Linear tableSequential structure , complex operation. Because it does not have to be stored in order, the chain table can achieve O(1) complexity when inserting, which is much faster than the other linear table sequence table. However, it takes O(n) time to find a node or access a specific number of nodes, while the corresponding time complexity of linear table and sequence table are O(logn) and O(1), respectively.
package com.fantj.dataStruct.listnode;
/**
* Chain structure
* Created by Fant.J.
* 2017/12/19 22:19
*/
public class Node {
//Data field
public long data;
//Node domain (pointer domain)
public Node next;
public Node(long value){
this.data = value;
}
/**
* Display method
*/
public void display(){
System.out.print(data+" ");
}
}package com.fantj.dataStruct.listnode;
/**
* Linked list
* Created by Fant.J.
* 2017/12/21 11:26
*/
public class LinkList {
//Head node
private Node first;
public LinkList(){
first = null;
}
/**
* Insert a node after the head node
*/
public void insertFirst(long value){
Node node = new Node(value);
node.next = first;
first = node;
}
/**
* Delete a node after the header node
*/
public Node deleteFirst(){
Node temp = first;
first = temp.next;
return temp;
}
/**
* Display method
*/
public void display(){
Node current = first;
while (current != null){
current.display(); //Print node
current = current.next;
}
}
/**
* Search method
*/
public Node find(long value){
Node current = first;
while (current.data != value){
if (current.next == null){
return null;
}
current = current.next;//Keep looking down
}
return current;
}
/**
* Delete method, delete according to data field
*/
public Node delete(long value){
Node current = first;
Node previous = first;//Represents the previous node
while (current.data != value){
if (current.next == null){
return null;
}
previous = current; //Extract the current node as the previous node (use the next node of the node to point to the next node of the deleted node)
current = current.next; //Keep looking down
}
if (current == first){
first = first.next;
}else {
previous.next = current.next;
}
return current;
}
}Source code: git address