Learn data structure and algorithm from scratch (2) linear list chain storage structure

The list

Chain storage structure
define
- The chain storage structure of a linear table is characterized by the use of a set of arbitrary storage units to store the data elements of a linear table, which can be continuous or discontinuous.
species
- chart
- Singly linked lists
  - Application: MessageQueue
  - Insert enqueueMessage(Message MSG,Long when).
  - Delete next ().
- Single loop linked list
- Double linked list
  - LinkedList
- Bidirectional circular linked lists
The advantages and disadvantages
- Advantages: Fast insertion and deletion
- Disadvantages: Does not support random access

Learning example

Based on the system API LinkedList mahjong group sorting

thought
Logical steps
1. Load all points into the corresponding linked list group
2. To combine all the points in a linked list
3. Put all the points in the corresponding linked list
4. Finally, the corresponding point list is installed in a new set

The code

/** * mahjong data Bean */
public class Mahjong {
    public int suit;// I'm not sure what I'm doing
    public int rank;// Count one, two, three

    public Mahjong(int suit, int rank) {
        this.suit = suit;
        this.rank = rank;
    }

    @Override
    public String toString(a) {
        return "("+this.suit+""+this.rank+")"; }}Copy the code

/** * with the system's own LinkedList structure to sort mahjong *@param list
 */
private void radixSort(LinkedList<Mahjong> list) {
    //1. Put all the points into the corresponding list group
    // create a set with a maximum of 9 points
    LinkedList[] linkedList = new LinkedList[9];
    // Initialize the 9 lists to hold all the corresponding points
    for (int i = 0; i < 9; i++) {
        linkedList[i] = new LinkedList();
    }
    while (list.size() > 0) {
        // Take the corresponding element and add it to the list
        Mahjong mahjong = list.remove();
        // ametaph. rank-1, which means the corresponding set subnames
        linkedList[mahjong.rank - 1].add(mahjong);
    }

    //2. Then add all the points in the list together
    for (int i = 0; i < linkedList.length; i++) {
        list.addAll(linkedList[i]);
    }

    //3. Add all points to the corresponding linked list
    // There are three suits, so we create three linked lists to represent the corresponding suits loaded
    LinkedList[] linkedLists =new LinkedList[3];
    for (int i = 0; i < 3; i++) {
        linkedLists[i] = new LinkedList();
    }

    // put the corresponding suit in the corresponding linked list
    while (list.size()>0){
        Mahjong mahjong = list.remove();
        linkedLists[mahjong.suit - 1].add(mahjong);
    }

    //4. Finally, put the corresponding point list into a new set
    for (int i = 0; i < linkedLists.length; i++) { list.addAll(linkedLists[i]); }}Copy the code

application

Dozens of data and multiple insertion operations

Write a two-way LinkedList CURD

Refer to the illustration
Write the code

/** * Created by yangk on 2019/1/29. *  ** Created by Yangk on 2019/1/29

public class CustomLinkedList<E> {

    /** ** the head of the list */
    transient Node<E> head;

    /** ** the end of the list */
    transient Node<E> tail;

    /** * The current list size */
    transient int size;

    /** * Store data */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }


    /** * returns the size of the current list **@return* /
    public int getSize(a) {
        return size;
    }

    /** * Stores the current data to the head of the list **@param e
     */
    public void addFirst(E e) {
        Node<E> h = head;
        // Create a node
        Node<E> newNode = new Node<>(null, e, head);
        head = newNode;

        if (head == null) {
            tail = newNode;
        } else {
            h.pre = newNode;
        }
        size++;
    }

    /** * Search node data by index **@param index
     */
    public E get(int index) {
        if (isPositionIndex(index)) {
            return searchNode(index).data;
        }
        return null;
    }


    /** * Add data to index **@param index
     * @param e
     */
    public void add(int index, E e) {
        addIndex(index, e);
    }

    /** * delete the first node */
    public E remove(a) {
        return removeFirst();
    }
    
    /** * delete the head node **@return* /
    private E removeFirst(a) {
        Node<E> h = head;
        if (h == null)
            throw new NoSuchElementException();
        return unlinkFirst(h);
    }

    private E unlinkFirst(Node<E> h) {
        // Delete data
        E deleData = h.data;
        // Find the back drive to delete
        Node next = h.next;

        // Clear the node
        h.data = null;
        h.next = null;

        // Set the current afterdrive to be deleted to the header of the linked list
        head = next;


        if (next == null) {
            tail = null;
        } else {
            next.pre = null;
        }
        h = null;

        size--;
        return deleData;
    }

    private void addIndex(int index, E e) {
        if (isPositionIndex(index)) {
            // Find the current index location to insert
            if (index == size) {
                linkLast(e);
            } else{ add(e, searchNode(index)); }}}/** * Adds a new node to the searchNode precursor **@param e
     * @param searchNode
     */
    private void add(E e, Node<E> searchNode) {
        // Find the searchNode precursor
        Node<E> snPre = searchNode.pre;
        // Create a node
        Node<E> newNode = new Node<>(snPre, e, searchNode);
        searchNode.pre = newNode;
        Snpre-next () = newNode; snpre-next () = newNode; snpre-next () = newNode
        if (snPre == null) {
            head = newNode;
        } else {
            snPre.next = newNode;
        }
        size++;
    }

    private Node<E> searchNode(int index) {
        // if index > size / 2, start at the end of the query, otherwise start at the head of the query
        if (index > (size >> 1)) {
            Node<E> t = tail;
            for (int i = size - 1; i > index; i--) {
                t = t.pre;
            }
            return t;
        } else {
            Node<E> h = head;
            for (int i = 0; i < index; i++) {
                h = h.next;
            }
            returnh; }}/** * stores data to the end of the current list **@param e
     */
    private void linkLast(E e) {
        // Get the end node data
        Node<E> t = tail;
        // Create new node data, because it exists at the end of the current node,
        // By default, the precursors of the currently added E are set to
        // The tail of the current list is now singly linked
        // The next step is to form the bidirectional list directly
        Node<E> newNode = new Node<>(t, e, null);
        // The new node points to the current tail node, and the tail node points to the new node
        tail = newNode;

        // If the tail node is empty, then the head is also empty
        if (t == null) {
            head = newNode;
        } else {
            t.next = newNode;
        }
        size++;
    }


    /** * create an empty constructor */
    public CustomLinkedList(a) {}private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    /** * define an internal node *  * bidirectional linked list requires precursors, backcursors, data */
    public static class Node<E> {
        /** * The precursor of the current node */
        private Node pre;
        /** * Data of the current node */
        private E data;
        /** * The current node's rear drive */
        private Node next;

        public Node(Node pre, E data, Node last) {
            this.pre = pre;
            this.data = data;
            this.next = last; }}}Copy the code

The test code

@Test
public void testCustomLinkedList() { CustomLinkedList<Integer> linkedList = new CustomLinkedList<Integer>(); linkedList.add(22); linkedList.add(2); linkedList.add(77); linkedList.add(6); linkedList.add(43); linkedList.add(76); linkedList.add(89); LinkedList. Add (0, 0);for (int i = 0; i < linkedList.size; i++) {
        int integer = linkedList.get(i);
        System.out.println("--CustomLinkedList--CustomLinkedList" +integer+"");
    }
    System.out.println("\n\n");
    Integer remove = linkedList.remove();
    System.out.println("--CustomLinkedList--CustomLinkedList" +remove);
    Integer remove1 = linkedList.remove();
    System.out.println("--CustomLinkedList--CustomLinkedList" +remove1+"");
    Integer remove2 = linkedList.remove();
    System.out.println("--CustomLinkedList--CustomLinkedList" + remove2 + "");


    System.out.println("\n\n");
    for (int i = 0; i < linkedList.size; i++) {
        int integer = linkedList.get(i);
        System.out.println("--CustomLinkedList--CustomLinkedList" +integer+""); }}Copy the code

The test results

Write a simple ArrayList CURD

public class CustomArrayList<E> {

    /** * the default empty element object */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /** * empty element data */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /** * The default element object */
    private Object[] elementData = null;

    /** * Capacity */
    private int size = 0;

    /** * The default capacity */
    private static final int DEFAULT_CAPACITY = 10;

    /** * maximum quantity ** TODO------------ minus 8
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE  - 8;

    /** * assigns an empty object */
    public CustomArrayList(a){
        elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /** * Externally specifies a capacity size to initialize *@param initCapacity
     */
    public CustomArrayList(int initCapacity){
        if (initCapacity > 0){
            elementData = new Object[initCapacity];
        }else if (initCapacity == 0){
            elementData = EMPTY_ELEMENTDATA;
        }else {
            throw  new IllegalArgumentException("Illegal Capacity: "+ initCapacity); }}/** * Add data */
    public boolean add(E e){
        // Determine whether to create capacity space
        checkIsNeedCapacity(size + 1);
        // Add Add data
        elementData[size++] = e;

        return true;
    }


    private void checkIsNeedCapacity(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    /** * The core code that opens up space *@param minCapacity
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return(minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }}Copy the code

Write a one-way linked list structure CURD

/** * Created by yangk on 2019/2/19. */

public class SingleLinked<T> {

    /** ** the head node */
    Node<T> head;
    /** * List length */
    int size = 0;

    /** * Add data to the linked list **@param data
     */
    public void add(T data) {
        Node node = new Node(data);
        if (head == null) {
            head = node;
            return;
        }
        Node<T> tmp = head;

        while(tmp.next ! =null) {
            tmp = tmp.next;
        }

        tmp.next = node;

        size++;
    }

    /** * adds data to the first location **@param data
     */
    public void addHead(T data) {
        Node node = new Node(data);
        if (head == null) {
            head = node;
            size++;
            return;
        }

        Node n = head;
        node.next = n;
        head = node;

        size++;
    }

    public void add(int index, T data) {
        Node node = new Node(data);
        if (index == 0) {
            addHead(data);
        } else {
            Node tmp = head;
            for (int i = 0; i < index - 1; i++) { tmp = tmp.next; } Node n = tmp.next; tmp.next = node; node.next = n; size++; }}/** * Clear all data */
    public void clear(a) {
        head = null;
        size = 0;
    }

    public boolean remove(int index) {/ / 2
        Node<T> tmp = head;
        if (index == 0) {
            Node<T> newHead = tmp.next;
            head = null;
            head = newHead;
            size--;
            return true;
        }
        if (index < size) { // 1 2 3 4 5 6 7 3
            for (int i = 0; i < index - 2; i++) {
                tmp = tmp.next;
            }
            Node<T> pre = tmp;
            // The node to be deleted
            Node<T> next = tmp.next;
            Node<T> p = tmp.next.next;
            pre.next = p;
            next = null;
            size--;
            return true;
        }
        return false;

    }


    /** * Node data */
    private class Node<T> {
        T data;
        Node<T> next;

        public Node(T data, Node<T> next) {
            this.data = data;
            this.next = next;
        }

        public Node(T next) {
            this.data = next; }}public void println(a) {
        if (head == null) return;
        Node n = head;

        while(n ! =null){
            System.out.println(n.data + "\n"); n = n.next; }}}Copy the code

Data structure series