Linear linked list & & single linked list

The concept of linked list
    The defect of array as data storage structure;
        In an unordered array, search is inefficient
        However, it is inefficient to insert an ordered array
        No matter in which array the deletion efficiency is very low
        After an array is created, its size is immutable
    Linked list:
        A linked list can be an ordered or unordered list
        The contents of the linked list are usually stored in scattered locations in memory
        The chain list consists of nodes, each of which has the same structure
        The node is divided into data domain and chain domain. Data domain is the content of the node, and chain domain is the pointer to the next node

Basic operation of linked list
    The establishment of linked list is also called the initialization of linked list:
        The first node in the list, we call it the head node. The structure of the head node is the same as that of the common node
    Usually we will specify it at the beginning of the list.
        The last node in the list is empty, which is expressed as NUL in the program to avoid throwing
 Null pointer exception.
class Node{
    //Define the beginning of a list
    public String id;
    public Node next;
    public Node() {

    }
    public Node(String id) {
        this(id,null);
    }
    public Node(String id,Node next) {
        this.id=id;
        this.next=next;
    }
}
public class Link {
    //Define head node
    Node head;
    public Link() {
        //Building tables
        //The header node will not put data
        head=new Node(); 
        head.next=null;
    }
    //Newly added
    public void addNode(String data) {
        /**
         * 1.Get header
         * 2.Find the last element through the header
         * 3.Put the new node after the last element
         */
        Node p=head;
        while(p.next!=null) {
            p=p.next;
        }
        Node temp=new Node(data);
        p.next=temp;
    }
    //Delete operation
    public void deleteNode(String data) {
        /**
         * 1.Get header
         * 2.Find the last element through the header
         * 3.Delete the last element
         */
        Node p=head;
        //Empty list direct return
        if(p.next==null) {

        }
        while(p.next!=null) {
            if(p.next.id.equals(data)) {
                p.next=p.next.next;
                break;
            }
            else {
                p=p.next;
            }
        }

    }
    //ergodic
    public void display() {
        Node p=head;
        while(p.next!=null) {
            System.out.println("->>"+p.next.id);
            p=p.next;
        }
    }
    //lookup
    public void findNode(String data) {
        /**
         * 1.Get header
         * 2.Find the element through the header
         * 3.Delete the last element
         */
        Node p=head;
        //Empty list direct return
        if(p.next==null) {

        }
        while(p.next!=null) {
            if(p.next.id.equals(data)) {
                System.out.println("data"+p.next.id);
                break;
            }
            else {
                p=p.next;
            }
        }

    }
    //Insert node
    public  void insertNode(String param,String data) {
        /*
         * param Indicates that the new node is to be inserted after the node
         * Get header
         * Find the node of param element through the header
         * Insert the new node after the node
         */
        Node p=head;
        while(p.next!=null) {
            if(p.next.id.equals(param)) {
                Node temp=p.next;
                Node insertNode=new Node(data);
                insertNode.next=temp.next;
                temp.next=insertNode;
                break;
            }else {
                p=p.next;
            }
        }
    }
    //Calculate list size
    public int size() {
        Node p=head;
        int n=0;
        while(p.next!=null) {

            p=p.next;
            n++;
        }
        return n;
    }
    public static void main(String[] args) {
        Link link=new Link();
        link.addNode("Group leader");
        link.addNode("division manager");
        link.addNode("Vice president in charge");
        link.addNode("general manager");
        link.display();
        System.out.println(link.size());
        link.deleteNode("division manager");
        link.display();
        System.out.println(link.size());
        link.insertNode("Group leader","division manager");
        link.display();
        System.out.println(link.size());
        System.out.println("=================");
        link.insertNode("general manager","chairman");
        link.display();
        System.out.println(link.size());

    }
}

Posted on Sat, 02 May 2020 20:01:12 -0700 by geus