Sequential tables in linear tables were introduced in the previous article

JAVA elementary must learn - linear table - sequence table

In these sections, we will understand the linked list in the linear list, and thoroughly grasp the linked list through the examples in LeetCode.

Don't talk nonsense, let's get to the point

content

definition:

Basic operation

traverse print

3. Tail plug

4, tail deletion

5. Skip the first n nodes to traverse the linked list

## definition:

A linked list is a non-consecutive, non-sequential storage structure on a physical storage unit , and the logical order of data elements is implemented through references in the linked list . A linked list consists of a series of nodes (each element in the linked list is called a node), and nodes can be dynamically generated at runtime. Each node consists of two parts: one is the data field that stores the data element, and the other is a reference to the next node object. Compared with the linear table sequential structure , the operation is complicated. Since it does not have to be stored in order, a linked list can achieve O(1) complexity when inserting, which is much faster than another linear list sequential list, but it takes O(n) to find a node or access a specific number of nodes time, and the corresponding time complexity of linear table and sequential table are O(logn) and O(1) respectively.

A linked list is composed of multiple nodes, the element value of the data field in a node and a reference next to the next object.

The definition says that a linked list consists of a series of nodes.

So we can learn linked list from the node first.

``define a node class public  class  ListNode { public int val ; //value public ListNode next; //Store the position of the next node //define the constructor public ListNode(){}; //No parameters public LIstNode(int val ){ this . val = val ;} // contains a parameter public ListNode(int val ,ListNode next){ this.val = val ; _ _ this .next=next; } // Contains two parameters }``

So we define a node class

Next, we define a LearnListNode to build a linked list and perform some basic operations on the linked list we built

``public  class  LearnListNode {    public  static  void  main (String[] args) {        //Represent the linked list by the head node        { //1, represents an empty linked list            ListNode  head  =  null ;           }        { //2, indicating a linked list with only one node object             ListNode  head  =  new  ListNode ();            head.val = 100 ;            head.next = null ;        }        //3, a linked list containing four nodes [100, 200, 300, 400]        ListNode  n1  =  new  ListNode ( 100 );          ListNode  n2  =  new  ListNode ( 200 );        ListNode  n3  =  new  ListNode ( 300 );        ListNode  n4  =  new  ListNode ( 400 );        n1.next = n2;        n2.next = n3;        n3.next = n4;        n4.next = null ;        ListNode head=n1;        //The special node in the linked list is the head and tail nodes, the head node has no predecessor node, and the tail node has no subsequent node, so n4 is the last node in this linked list, its next = null, That is, it does not point to any node.``

The above is to define an empty linked list, a linked list with one node, and a linked list with four nodes. It should be noted that the linked list is represented by the head node, so it is necessary to specify the head node of the linked list. A node represents a linked list.

After defining the node class, a linked list with four nodes is connected in the LearnListNode, and the head node is used to represent this linked list. Next, we can perform some basic operations in the linked list.

## Basic operation

### traverse print

//1, first construct a node and put e into it

ListNode node =new ListNode(e);

//2, let the node node to be inserted point to the next node of the head node

return node;

### 3. Tail plug

private static ListNode tail (ListNode head, long e){

ListNode node = new ListNode(e);

node.next = null;

return node;

}

while(last.next != null){

last = last.next;}

//At this time last is the last node

last.next = node;

### 4, tail deletion

private static ListNode tail (ListNode head) {

//empty list

return null;

}

//Go here to indicate that the linked list is not empty, and handle the case of a non-empty linked list

while(last.next.next!=null){

last=last.next;

}//After the loop ends, last points to the penultimate node

last.next=null;//Let the next of the penultimate node point to null, thus deleting the original last node

### 5. Skip the first n nodes to traverse the linked list

privatestatic void skip the first n nodes and traverse the linked list (ListNode head, int n){     //skip the first n nodes     ListNode cur=head;     for (int i=0; i <n ; i++) {         cur=cur .next;     }     while(cur!=null){         System.out.println(cur.val);         cur=cur.next;     } }

This section introduces the definition of linked list, node class, and some basic operations of linked list. If it is helpful to you, please support three times. More knowledge about linked list will be continuously updated later, such as linked list OJ topics, etc.