java-playing linked list-1

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

linked list

content

definition:

Basic operation

traverse print

1, head plug

2, header deletion

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.

  1. define a node class
  2. public class ListNode {
  3. public int val ; //value
  4. public ListNode next; //Store the position of the next node
  5. //define the constructor
  6. public ListNode(){}; //No parameters
  7. public LIstNode(int val ){
  8. this . val = val ;} // contains a parameter
  9. public ListNode(int val ,ListNode next){
  10. this.val = val ; _ _
  11. this .next=next;
  12. } // Contains two parameters
  13. }

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

  1. public class LearnListNode {
  2. public static void main (String[] args) {
  3. //Represent the linked list by the head node
  4. { //1, represents an empty linked list
  5. ListNode head = null ;
  6. }
  7. { //2, indicating a linked list with only one node object [100]
  8. ListNode head = new ListNode ();
  9. head.val = 100 ;
  10. head.next = null ;
  11. }
  12. //3, a linked list containing four nodes [100, 200, 300, 400]
  13. ListNode n1 = new ListNode ( 100 );
  14. ListNode n2 = new ListNode ( 200 );
  15. ListNode n3 = new ListNode ( 300 );
  16. ListNode n4 = new ListNode ( 400 );
  17. n1.next = n2;
  18. n2.next = n3;
  19. n3.next = n4;
  20. n4.next = null ;
  21. ListNode head=n1;
  22. //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

while(head !=null){

System.out.println(head.val);

head=head.next;}

1, head plug

public static ListNode header (ListNode head, long e){

//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

node.next = head;

//3, modify the head node of the linked list to node

  return node;

2, header deletion

private static ListNode header (ListNode head){

return head.next}//Directly changing the object pointed to by the head node is the head deletion

3. Tail plug

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

ListNode node = new ListNode(e);

node.next = null;

if(head == null){

return node;

}

while(last.next != null){

last = last.next;}

//At this time last is the last node

last.next = node;

return head;

4, tail deletion

private static ListNode tail (ListNode head) {

//empty list

if(head==null){

return null;

}

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

ListNode last=head;

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

return head;//Return the head node of the linked list

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. 

Related: java-playing linked list-1