Since we are talking about linear and linked lists in this section, it is important to understand the concept of data structures. Firstly, data structure is generally divided into logical structure and physical structure. Logical structure refers to the relationship between data object elements, while physical structure refers to the storage structure of data. Logical structure mainly includes set structure, linear structure, tree structure, graph structure, and physical structure mainly includes chain storage and linear storage. In the analysis of data structure, logical structure and physical structure complement each other.

The data locations of linear tables are independent, and one location follows the next, with data stored at the 0th location a1, the first location A2, and so on, until the last data an. For example, if you want to delete one of the data a2, then A3 will move to the original a2, a4 will move to a3, so that every data after A2 will move forward one bit, which makes the linear storage data in the deletion process becomes inefficient. On the contrary, the linear storage structure stores data sequentially, without Pointers to the location of the guide operation, its query speed is relatively fast.

Different from the linear storage structure, the chain storage structure can add variables in its own quantity and point to the previous or the next data by using the additional variables. When inserting or deleting data, it can be realized by changing the pointing of the additional variables without changing the storage address of the data before and after. For example, if a2 data is also deleted, after A2 data is deleted, the backward add-on variable of A1 will point to A3 and the forward add-on variable of A3 will point to A1. In this way, the position of the data after A2 data is not changed, but the data position of the additional variables of A1 and A3 will be changed. In the Java language, the more obvious linear table, linked table is ArrayList, LinkedList, studied JDK source should know, these two tables have their own add, delete, query methods, the two tables in the implementation of these three methods are also very different. Let's compare the add() methods of ArrayList and LinkedList. Note: this example uses JDK18.Source code display.// ArrayList implements add()
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
}
The add() method does not specify the location of the data object to be added
// The implementation is also simpler, assigning data objects directly to arrays
// LinkedList implements add()
public void add(int index, E element) {
        checkPositionIndex(index);
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
        // assert succ ! = null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }
Copy the code

This section is here, so as to avoid visual fatigue, source code part of the ape children’s shoes can be interested in their own in-depth study. In the next section, we’ll take a look at stack and queue data structures, so keep an eye out for future updates, haha!

More exciting to wechat public number [Lao Wang said programming] >>>