The beauty of data structure and algorithm -- review of single linked list

1. Course content

For details, please refer to the course "beauty of data structure and algorithm" on "geek time": 07 | linked list (Part 2): how to write the correct linked list code easily? (geekbang.org)

2. After class practice

code:

node

package dataStruct;

/**
 * @ClassName Node
 * @Version 1.0
 * @Author Wulc
 * @Date 2022-01-28 10:54
 * @Description Linked list node
 */
public class Node<T> {
    //Data information
    public T data;
    //Next node reference
    public Node next;

    public Node(T data) {
        this.data = data;
    }
    
    //Add node
    public void add(T data) {
        if (this.next == null) {
            this.next = new Node(data);
        } else {
            this.next.add(data);
        }
    }

    //Add node
    public void add(Node node) {
        if (this.next == null) {
            this.next = node;
        } else {
            this.next.add(node);
        }
    }
}

Linked list:

package dataStruct;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName ListNode
 * @Version 1.0
 * @Author Wulc
 * @Date 2022-01-28 10:54
 * @Description Linked list
 */
public class ListNode<T> {
    //Root node location
    public int foot;
    //Linked list length
    public int length;
    //current node 
    public Node root;
    //Head node
    public Node head;

    public ListNode() {
        this.head = new Node("Head");
    }

    //Determine whether the linked list is empty
    public boolean isEmpty() {
        if (length == 0 || this.root == null) {
            return true;
        } else {
            return false;
        }
    }

    //Determine whether the linked list contains a value
    public boolean contain(T data) {
        Node cur = this.head.next;
        while (cur != null) {
            if (cur.data.equals(data)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //Determine whether the linked list contains a node
    public boolean contain(Node node) {
        Node cur = this.head.next;
        while (cur != null) {
            if (cur == node) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //Get the length of the linked list
    public int size() {
        return this.length;
    }

    //Add node
    public void addNode(T data) {
        if (this.isEmpty()) {
            this.root = new Node(data);
            //The next node of the head node is the first node of the linked list
            this.head.next = this.root;
        } else {
            this.root.add(data);
        }
        this.length++;
    }

    //Add node
    public void addNode(Node node) {
        if (this.isEmpty()) {
            this.root = node;
            //The next node of the head node is the first node of the linked list
            this.head.next = this.root;
        } else {
            this.root.add(node);
        }
        this.length++;
    }

    //Output linked list
    public Object[] print() {
        Object obj[] = new Object[this.length];
        int i = 0;
        //Traverse from the first linked list node
        this.root = this.head.next;
        while (this.root != null) {
            obj[i++] = this.root.data;
            this.root = this.root.next;
        }
        this.root = this.head.next;
        return obj;
    }

    //Single linked list inversion: as long as the next pointer of each node on the linked list points to its predecessor node, the single linked list inversion can be completed
    public void reserve() {
        Node pre = null, next = null;
        this.root = this.head.next;
        while (this.root != null) {
            next = this.root.next;
            if (next == null) {
                //Ensure that the next of the head node points to the first node of the linked list
                this.head.next = this.root;
            }
            this.root.next = pre;
            pre = this.root;
            this.root = next;
        }
    }

    //Link detection in the linked list 1: fast and slow pointer method. If the slow pointer and fast pointer meet, there is a ring. If they do not meet, there is no ring
    public boolean ifHasLoopV() {
        //p1 is the slow pointer, stepping one grid at a time
        Node p1 = this.head.next;
        //p2 is the fast pointer, stepping two spaces at a time
        Node p2 = this.head.next.next;
        int i = 0;
        while (p1 != null && p2 != null) {
            if (p1 == p2) {
                return true;
            }
            if (p2.next.next == null) {
                return false;
            }
            p1 = p1.next;
            p2 = p2.next.next;
        }
        return true;
    }

    //Link detection in the linked list 1: footprint method, traverse the linked list. If you repeatedly traverse a node, there are links
    public boolean ifHasLoopV1() {
        List<Node> list = new ArrayList<>();
        Node cur = this.head.next;
        while (cur != null) {
            if (list.contains(cur)) {
                return true;
            }
            list.add(cur);
            cur = cur.next;
        }
        return false;
    }

    //Two ordered linked lists are merged (in descending order), and the current linked list and parameter linked list are merged into a new linked list
    public ListNode mergeSortedLinkList(ListNode listNode) {
        ListNode tListNode = new ListNode();
        this.root = this.head.next;
        while (this.root != null && listNode.root != null) {
            if (this.root.data.toString().compareTo(listNode.root.data.toString()) < 0) {
                tListNode.addNode(new Node(this.root.data));
                this.root = this.root.next;
            } else {
                tListNode.addNode(new Node(listNode.root.data));
                listNode.root = listNode.root.next;
            }
        }
        while (this.root != null) {
            tListNode.addNode(new Node(this.root.data));
            this.root = this.root.next;
        }
        while (listNode.root != null) {
            tListNode.addNode(new Node(listNode.root.data));
            listNode.root = listNode.root.next;
        }
        return tListNode;
    }

    //Delete the penultimate node of the linked list: fast and slow pointer method
    public void removeLastN(int n) {
        if (n == length) {
            this.head.next = this.root.next;
            this.length--;
        }
        if (n < length) {
            Node p1 = this.head;
            Node p2 = this.head;
            int i = 0;
            while (i < n) {
                p2 = p2.next;
                i++;
            }
            while (p2 != null) {
                p1 = p1.next;
                p2 = p2.next;
                if (p2.next == null) {
                    this.root = p1;
                    //Delete the penultimate node
                    this.root.next = p1.next.next;
                    this.length--;
                    break;
                }
            }
        }
    }

    //Find the middle node of the linked list
    public Node getMiddleNode() {
        int i = 0;
        this.root = this.head.next;
        if (this.length % 2 == 1) {
            while (i++ < this.length / 2) {
                this.root = this.root.next;
            }
        } else {
            while (i++ < this.length / 2 - 1) {
                this.root = this.root.next;
            }
        }
        return this.root;
    }

}

3. Summary

Because it was close to the Chinese new year, I was relatively idle, so I used the points given by the company to buy the course "the beauty of data structure and algorithm" on geek time. It aims to consolidate the foundation and improve the code ability and logical thinking ability.

Except that I wrote some Linked lists manually during the data structure course in my sophomore year, and then I hardly used the Linked lists in the course design, completion design and actual development. LinkedList, LinkedHashMap and LinkedHashSet are common Linked list structures in java. Generally speaking, Linked is added to explain the underlying structure and Linked list is added.

Specifically

For example, LinkedList and ArrayList

The underlying data structure of LinkedList is linked list, which has no fixed size and does not need to be expanded. Fast insertion and deletion.

The underlying data structure of ArrayList is array. The default length of array is 10. When the storage capacity reaches two-thirds, it will be automatically expanded by 1.5 times (that is, apply for a space of 1.5 times the original size and copy all the contents of the original to the new space). Therefore, ArrayList is not friendly to insert and delete operations, but thanks to the subscript index addition of the underlying array structure, the query speed is fast.

LinkedHashMap and HashMap

LinkedHashMap inherits from HashMap, but has a "two-way linked list". Because there is a "two-way linked list", LinkedHashMap can be output according to the insertion order of elements (only the output order can be output according to the insertion order). However, the order of storage structure elements of LinkedHashMap and HashMap is the same, and they are sorted in ascending order according to the key, because the put method of LinkedHashMap is the same as that of HashMap.

The structure of HashMap is hash table + linked list, as follows:

HashMap.put() underlying implementation

LinkedHashMap.put and HashMap The underlying implementation principle of put () is the same, except that LinkedHashMap has an additional two-way linked list to store the entry.

LinkedHashSet and HashSet

First of all, the values in the HashSet are not repeatable. In fact, the underlying HashSet uses HashMap to store elements. Because the add method of HashSet calls the put method of HashMap, HashSet The value of add is HashMap The key of put. Because the key of HashMap cannot be repeated, HashSet The value of add will not be repeated.

When HashMap saves data, it will calculate a hashCode value according to the key to determine the storage location in the hash table. The hash value is calculated by the system and has a certain randomness, so HashSet The value of add (equivalent to the key in HashMap) is stored in memory, and it is also stored in disorder according to the value of hashCode.

Of course, there is a problem here. Since the value of hashSet exists in hashMap in the form of key, but the key in hashMap is orderly, and the value of hashSet stored in hashMap with hashMap key is disordered? In fact, this problem is easy to explain, that is, hashSet only borrows the storage structure of hashMap, but will not use the corresponding key sorting optimization algorithm in hashMap. Therefore, the hashSet is indexed according to the hash code.

LinkedHashSet inherits from HashSet, and the underlying layer uses the LinkedHashMap of the parent HashSet to save all elements. Therefore, LinkedHashSet and LinkedHashMap can be output in order according to the input order.