preface

In the last article we looked at arrays, which are very basic data structures. In the case of arrays, we know that arrays are stored sequentially in memory and arranged linearly, so they have “random access” capability, but are inefficient for delete and insert operations.

Today we are going to explore a new data structure, linked list. What is a linked list? What’s the point of learning linked lists?

What is a linked list

Linked list is a very important data structure, which is widely used. It is very easy to make mistakes when writing linked list code. Therefore, linked list is often used to test whether the logic of the interviewer is rigorous in the interview.

Unlike arrays, which require contiguous memory space, linked lists do not require contiguous memory space (that is, contiguous or non-contiguous). Instead, linked lists use Pointers (the Next field) to concatenate discrete chunks of memory. All linked lists are stored randomly. Let’s look at what the individual nodes in the linked list look like, as follows:

Here you can see Data and Next. Explain:

  1. Data: data field for storing node values;
  2. Next: the pointer that records the address of the next node, also called the successor pointer field;

The next pointer is the main reason a linked list can concatenate discrete chunks of memory.

So next, today we will understand the three most common linked list structure, respectively is single linked list, bidirectional linked list, circular linked list and so on.

1. The singly linked list

Let’s take a look at the structure of a single linked list, as shown below:

In the figure, we can see that each single node in a single linked list contains two parts, namely data and next. I won’t explain it here. In addition to that, we have a head. What is this? This is actually the head node, the first node in the list. Similarly, the last node of the list is called the tail node. The tail node is special because its next pointer points to null, which is the last node of the list.

2. Bidirectional linked lists

Let’s first take a look at the structure of the bidirectional list, as shown in the figure below:

As can be seen from the figure, bidirectional linked lists are slightly more complicated than single linked lists. In single linked lists, there is only one direction, and each node has only one successor pointer next, while bidirectional linked lists support two directions. Each node has not only one successor pointer next, but also one predecessor pointer Pre. And the first node’s predecessor, pre, points to null.

Consider: What are the advantages and disadvantages of using two Pointers to each node of a bidirectional list?

As can be seen from the figure, single-linked lists only support traversal in one direction, while bidirectional lists support traversal in two directions. The advantage is that bidirectional lists are much more flexible than single lists, but this flexibility comes at a cost. The disadvantage is that if you store the same number of elements, two Pointers to a bidirectionally linked list can be a waste of space compared to a single list.

3. Circular linked lists

Referring to cyclic lists, can be divided into unidirectional cyclic lists and bidirectional cyclic lists, in fact, are derived from the above two types of lists. As shown below:

The trailing pointer to a single linked list points to NULL, while the trailing pointer to a circular linked list points to the head of the list. As we can see in the figure, the circular linked list is connected from end to end like a loop.

The basic operations of linked lists

Above we briefly discussed several common linked list structure, let’s use a single linked list as an example, using a graphical way to see how to add, delete, change, and check the linked list, before we start to create a class. The code is as follows:

public class MyLinked {

    private Node head;

    private Node last;

    private int size;
    
    private static class Node{
        
        public int data;

        public Node next;

        public Node(int data){
            this.data=data; }}}Copy the code

The most important thing about linked list operations is that

1. Find nodes

When an array is looking for an element, it can quickly locate the element by subscript. But linked lists do not have this ability, to find an element in the list, you have to start from the beginning of the node to find the element, or not. The time complexity is O(N) because it is traversed from the beginning. The node search process of linked list is shown in the figure below:

The code for finding the specified node is as follows:

/** * gets the element ** at the specified position@paramIndex Specifies the location *@return
 * @throws Exception
 */
public Node find(int index) throws Exception {
   if (index < 0 || index > size) {
      throw new IndexOutOfBoundsException("Out of range of actual list nodes!");
   }
   Node temp = head;
   for (int i = 0; i < index; i++) {
      temp = temp.next;
   }
   return temp;
}
Copy the code

2. Update nodes

Updating a node in a linked list is similar to the search process, which is also iterated from the beginning to find the location of the node to be updated, and then directly assign the value. The node updating process of linked list is shown in the figure below:

3. Add nodes

There are three situations to consider when nodes are added in the linked list, namely, head new, middle new and tail new.

Let’s take a look at the simplest case of tail addition. Just iterate through the list, and if next points to null on the current node, the next pointer on the current node points to the new node. As shown below:

Now we’re going to look at header inserts, because at the head of the list, we don’t need to walk through the list. We’re going to add this node firstnextPointer to the head of the original listhead, and then change the position of the head node to the new node. As shown below:

At this time, we need to traverse the linked list. The first step: set the next pointer of the newly added node to the node at the newly added position. The second step: set the next pointer of the pre-added node at the newly added position to the new node. This process should be paid attention to, do not reverse the order, otherwise it is easy to break the linked list. As shown below:

The code for the new node at the specified location is as follows:

 /** * New element ** at the specified position@param data
 * @param index
 * @throws Exception
 */
public void insert(int data, int index) throws Exception {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Out of range of actual list nodes!");
        }
        Node insertNode = new Node(data);
        if (size == 0) {
            // Add an empty list
            head = insertNode;
            last = insertNode;
        } else if (index == 0) {
            // The header is added
            insertNode.next = head;
            head = insertNode;
        } else if (size == index) {
            // add a new tail
            last.next = insertNode;
            last = insertNode;
        } else {
            // Get the element before the new position
            Node preNode = find(index - 1);
            insertNode.next = preNode.next;
            preNode.next = insertNode;
        }
        // The actual list length is +1
        size++;
}
Copy the code

4. Delete the node

The deletion of nodes in linked lists also needs to consider three cases, which are: head deletion, middle deletion and tail deletion.

Let’s take a look at the simplest tail deletion case. When traversing the next-to-last node of the list, we simply point the next node of that node to null. As shown below:

Next we will look at header deletion. When deleting a linked list header node, we only need to change the header node to the original header node and the next node to the new header node. As shown below:

Finally, let’s look at the intermediate deletion case. In this case, the key is to find the leading node of the node to be deleted. Change the next node of this leading node to the interface of the next node of the node to be deleted. As shown below:

The code for the new node at the specified location is as follows:

/** * removes the list element ** at the specified position@paramIndex Specifies the location *@returnDeleted element *@throws Exception
*/
public Node delete(int index) throws Exception {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Out of range of actual list nodes!");
        }
        Node removeNode = null;
        if (size == 0) {
            // Delete the header
            removeNode = head;
            head = head.next;
        } else if (size - 1 == index) {
            // delete the tail
            // Get the element before the deleted position
            Node preNode = find(index - 1);
            removeNode = preNode.next;
            preNode.next = null;
            last = preNode;
        } else {
            // Delete
            // Get the element before the deleted position
            Node preNode = find(index - 1);
            removeNode = preNode.next;
            preNode.next = preNode.next.next;
        }
        // The actual length of the list is -1
        size--;
        return removeNode;
}
Copy the code

conclusion

This paper briefly introduces the linked list this data structure, we know that the advantages of the linked list is variable size, insert and delete efficiency is very high. The disadvantage is that if you look for an element, you have to start from scratch, so the query is inefficient.