preface

Linked lists, like arrays, are linear data structures. The operations of linked lists in algorithms are generally directed at one-way lists, because one-way lists are simpler but more capable of thinking. Although singly linked list is simpler, but want to write a list of code is not an easy thing, master list are a few key points: the first is to avoid the loss of pointer, and then we can introduce the sentinel to simplify the list of operation, the clever use of double pointer can also write a more efficient and concise list algorithm.

What is a linked list

A linked list is a storage structure that is not contiguous or sequential on a physical storage cell, but is logically contiguous. The logical order of each data element in the list is achieved through Pointers in the list.

A linked list consists of a series of nodes (each element of the list is called a node) that can be dynamically generated at run time. Each node of the linked list should have at least two parts: one is to store the element information of the node, and the other is to store the next pointer to the address of the next node.

Linked lists are a little more complex than arrays, and there are some essential differences.

The difference between linked lists and arrays

Linked lists, like arrays, are linearly stored data structures. Arrays require contiguous memory space, so the memory requirements are relatively high, because even if the total free memory in memory is enough, but if the memory is not contiguous, or the contiguous memory space is not enough to initialize the current array, the array will not initialize successfully; Linked lists require less memory because they do not require contiguous memory space. There are also essential differences between linked lists and arrays in the following operations:

• Insert elements

When inserting an element into an array, all elements after the insertion position need to be moved back one bit. Therefore, the worst time complexity of inserting an element into an array is O(n), while the linked list can reach O(1), because it only needs to change the pointer pointing to the insertion position to complete the element insertion.

• Remove elements

The same is true for deleting an element. An array needs to move all the elements after the deleted position forward one bit, so the worst time complexity is O(n), while a linked list does not. To delete an element in a linked list, you only need to change the pointer pointer, and the time complexity is O(1).

• Random fetch element

Because the space of array is continuous, the time complexity of randomly acquiring an element can reach O(1), but the time complexity of linked list is not good. The time complexity of linked list randomly acquiring an element needs to be traversed from the beginning node, so the worst time complexity is O(n).

• To obtain the length of the

The time to get the length of an array is O(1), while the list can only be traversed from the beginning to the end of the list, so the time to get the length of the list is also O(n).

Common list types

There are three common types of linked lists: unidirectional, bidirectional, and circular.

Singly linked list

One-way linked list refers to that each node maintains not only its own node information, but also a next pointer pointing to the next node. The next pointer of the last node in the list points to NULL, as shown in the figure below. It is a one-way linked list:

The first node in the linked list are called “nodes”, the first node is used to record the list of base address, normally we are through the head node to traverse the whole list, until a certain node next = null, said list has ended, through traversing, we can get the whole list of length, and each node in the list.

Unidirectional linked list is very popular in algorithm problems, because it is simple to operate, but it can also examine the thinking, especially linked list inversion, ordered linked list combination and other operations, which is very important, and linked list inverse to the top priority, we will analyze these two problems.

Two-way linked list

Compared with unidirectional lists, bidirectional lists have a prev pointer to point to the previous node, as shown below:

Bidirectional linked lists are relatively rare in algorithms, but they are widely used in practical projects. For example, Java JUC extensively uses bidirectional linked lists. Compared with unidirectional linked lists, bidirectional linked lists also have advantages, for example, given a Node Node, to delete it from the linked list. In the case of a one-way list, the deletion operation can only be performed by traversing from the beginning to find the previous node of the node, whereas a bidirectional list does not need to find the previous node of the current node through the prev pointer.

Circular linked list

A circular list is connected end to end. For example, in a one-way list, the next pointer of the last node points to the head node to form a circular list. In a bidirectional linked list, the prev pointer of the head node points to the tail node and the next pointer of the tail node points to the head node, which also forms a circular linked list.

The basic operations of linked lists

The basic operation of linked list is the same as add, delete, change and check. Next, we will see how to add, delete, change and check the linked list respectively.

Before adding, deleting, modifying, and checking, we initialize a linked list:

// Define the list node
public class ListNode {
    public int val;// The value in the node
    public ListNode next;// Pointer to the next node

    public int getVal(a){
        return this.val;
    }

    ListNode(int x) {
        val = x;
        next = null; }}Copy the code

// Initializes a linked list based on an array
package com.lonely.wolf.note.list;
public class ListNodeInit {
    public static ListNode initLinkedList(int[] array) {
        ListNode head = null, cur = null;
        for (int i = 0; i < array.length; i++) {
            ListNode newNode = new ListNode(array[i]);
            newNode.next = null;
            if (i == 0) {// Initialize the header node
                head = newNode;
                cur = head;
            } else {// Continue to insert nodes one by onecur.next = newNode; cur = newNode; }}returnhead; }}Copy the code

Gets the list length

In a one-way list, obtaining the length of a list requires traversing backwards from the beginning node to the end of the list. So the time complexity of getting a linked list is also O(n) :

public static int getListLength(ListNode head){
    int length = 0;
    while (null! = head){ length++; head = head.next; }return length;
}
Copy the code

Find nodes

If you need to find a specified node, or the NTH node, the search method is also the same as the length of the linked list, starting at the head node, and then comparing or counting until you find the desired node, so the worst time to find a node is also O(N).

The new node

If we need to insert a node at the specified location of the specified list, we need to consider the following:

• Whether the current insertion position exceeds the length of the linked list.
• Whether the currently specified list is empty.
• Is the current insertion position at the top, bottom, or middle of the list?

Here is an example of inserting an element into a specified position in a specified list:

public static ListNode insertNode(ListNode head, ListNode insertNode, int position) {
        if (null == head){// Note that the current list is empty
            return insertNode;
        }
        int size = ListNodeInit.getListLength(head);// Get the list length
        if (position < 0 || position > size + 1) {// Handle out-of-bounds
            return head;
        }
        if (position == 1) {// Insert the header (for lists, usually from 1)
            insertNode.next = head;
            head = insertNode;
            return head;
        }

        // If it is not inserted into the head of the list, then we need to find the node before the insertion position
        ListNode prevNode = head;
        int i = 1;
        while (i < position-1) {// Traverse to the previous node of position
            prevNode = prevNode.next;
            i++;
        }
        // Insert the pointer into the list. If the pointer is missing, it will break the list
        insertNode.next = prevNode.next;/ / 1
        prevNode.next = insertNode;/ / 2
        return head;
    }
Copy the code

If we want to insert a node with val=5 at position 4, we need to find node 3 (preNode). If we execute the code commented 2 above: Prenode. next = insertNode, then the following is the case (the dotted pointer indicates that it has been changed) :

At this time, we found that the original linked list was disconnected, that is, node 4 could not be found. Therefore, when inserting the node, we must connect the new node to the original linked list first to prevent pointer loss.

An important point here, please note that linked list operations must be careful of pointer loss.

Remove nodes

Deleting a node is similar to inserting a node. We also need to consider all kinds of boundary conditions. We should not think that these boundary judgments are trivial.

If node 3 is to be deleted, then pNode is 2 and deleteNode is 3. The first step to deleteNode 3 is to first point pointer p1 to 4 and then disconnect pointer p2 to complete node deletion.

Here is an example of deleting a node:

public static ListNode deleteNode(ListNode head,int position) {
        if (null == head){// The linked list is empty
            return null;
        }
        int length = ListNodeInit.getListLength(head);// Get the list length
        if (position <= 0 || position > length){// Delete position invalid
            return head;
        }

        // Delete the header node
        ListNode pNode = head;
        if (position == 1){
            head.next = null;// Disconnect the head to prevent memory leaks
            return pNode.next;// Set the new head
        }

        int count = 1;
        while (count < position - 1) {// Find the node before the deleted node
            pNode = pNode.next;
            count++;
        }

        // The disconnect process is shown below
        ListNode deleteNode = pNode.next;// Find the node to delete
        pNode.next = deleteNode.next;
        deleteNode.next = null;// Disconnect the deleted node from the linked list to prevent memory leaks
        return head;
    }
Copy the code

Update the node

If you have mastered the previous query, insert and delete operations, then the update is simple. If you just update val of the node, you can simply replace it by traversing to find the node. If you want to change the position of a node, you can delete the original node first and then insert it.

How to write bug-free linked list code

If you want to write a piece of BugFree code when working with linked lists, consider at least four scenarios each time:

1. If the linked list is empty, whether the desired effect can be achieved.
2. There is only one linked listheadNode, can achieve the desired effect.
3. Linked list contains only two nodes, can achieve the desired effect.
4. If the logic is handled at the head node or the tail node (such as insert and delete operations), the desired effect can be achieved.

If none of the above scenarios is a problem, then the code is basically fine.

Important algorithms for linked lists

The operation of linked lists is very challenging to the programmer’s mind, which can cause pointer loss or boundary handling errors if you are not careful. Now that you’ve mastered the basics of adding, deleting, modifying, and checking lists, let’s move on to some slightly more complex operations.

Merge ordered linked lists

Problem 21 in Leetcode: Merge two ascending lists into a new ascending list and return the new list formed by concatenating all nodes of a given two lists.

It’s not hard, and leetcode defines it as a simple level, but the point of this problem is to have an ordered list, and it needs to be organized after merging, so we don’t know who the head node of the new list is, and we can do this without any tricks, but we have to make all kinds of judgments, So we’re going to introduce another technique here, which is to introduce sentry nodes.

The so-called sentinel node is to define a virtual node. In this case, we can define a sentinel node as the head node. In this way, after judging the size of the elements in the two linked lists, we just need to insert the node with smaller elements into the next node of the sentinel node. The next node that finally returns to the sentinel node is the head of the combined ordered list.

public static ListNode mergeTwoList(ListNode head1,ListNode head2){
        ListNode sentryNode = new ListNode(-1);// The sentinel node
        ListNode curr = sentryNode;
        while (null! = head1 &&null! = head2){if (head1.val < head2.val){// If list 1 has smaller nodes, list 1 goes backwards
                curr.next = head1;
                head1 = head1.next;
            }else {// If list 2 has smaller nodes, list 2 goes backwards
                curr.next = head2;
                head2 = head2.next;
            }
            curr = curr.next;
        }
        // There is at most one remaining node in the list, and it may be all finished. The nice thing about the list is that you don't need to continue the loop
        curr.next = null == head1 ? head2 : head1;// If both of them are Null, then it doesn't matter if either of them are Null
        return sentryNode.next;// The next node to return to the sentinel node is the head node of the new list
    }
Copy the code

List inversion

List inversion can be said to be the essence of the operation of one-way linked lists, and list inversion is also a function that must be learned to learn linked lists.

In LeetCode, there are a lot of topics about list inversion, of course, no matter how many topics there are, once you have mastered the basics, the other thing is to take a few more steps, such as inversion in a given interval, etc.

If you are given the head node of a single linked list, reverse the list and return the reversed list.

The requirement of this problem is very simple, among which the most critical is still to prevent pointer loss. We still take the one-way linked list at the beginning of the article as an example, we reverse the linked list from the head, so first we need to point the pointer P1 in the following figure to the previous node, because the current is the head node, so its previous node is NULL. If we set p1 to null, the linked list will be broken, because the second node and subsequent nodes are missing, so before reversing a node, we must record the next node of this node.

When the first node is reversed, then node 2 is processed, so we still need to record the next node of node 2, namely node 3:

Again, where does p2 point to? Obviously should be pointing at the node 1, but this time we can’t find the node 1, so in order to find the node 1, above the first step in the inversion, we also need to record a pre node, which is at the time of each loop, will need to the current node (that is, a reverse node under the pre nodes), So we can make sure we don’t lose contact.

Once we’ve done that, we can continue to reverse until we’ve reversed the entire list. The relevant implementation code is as follows:

public static ListNode reverseByDirect(ListNode head){
        if (null == head || null == head.next){// Empty or only one node without inversion
            return head;
        }
        ListNode pre = null;// Record the previous node
        ListNode curr = head;// Record the current inverted node
        while (null! = curr){ ListNode next = curr.next;// Record a node
            curr.next = pre;// Point the current node next to the node that has been reversed
            pre = curr;
            curr = next;
        }
        return pre;// Finally, pre is the last node of the original list, which is the head node of the new list
    }
Copy the code

We mentioned the clever use of sentry node when we realized the combination of ordered linked lists. In fact, sentry node can also be used to realize the inversion of linked lists. The main steps of realizing the inversion of linked lists by sentry are as follows:

1. Define a sentinel node.
2. Start traversing the original linked list, inserting each node in turn after the sentinel. Note that it is inserted after the sentinel each time, so that when all the inserts are complete, the next node of the sentinel is the last node in the original list.

With the introduction of sentinel nodes, the inversion of linked lists is simplified to the insertion of linked lists. Examples of related code are as follows:

public static ListNode reverseBySentryNode(ListNode head){
        if (null == head || null == head.next){// Empty or only one node without inversion
            return head;
        }

        ListNode sentry = new ListNode(-1);// The sentinel node
        ListNode curr = head;
        while (null! = curr){ ListNode next = curr.next;// Record a node to prevent loss of contact
            curr.next = sentry.next;
            sentry.next = curr;// The current node should be connected to the sentry
            curr = next;
        }
        return sentry.next;
    }
Copy the code

Find the penultimate KTH node

Question 22 in the offer of Sword Finger is to find the KTH node from the bottom of the linked list (the list counts from 1), which is an interesting problem. The normal simple and rough idea is to find the length N of the linked list first, and then the n-k+1 node is the KTH node from the bottom of the list. Although this solution is feasible, Time is also O(n), but it requires traversing the list twice, so can we do that by traversing the list once?

In arrays we mentioned that the idea of double Pointers is very important, and in linked lists it’s the same idea, and you can do this very quickly with fast or slow Pointers.

Let’s think about going from the last KTH node to the end of the list, and notice that the end doesn’t refer to the last KTH node, it’s null, so obviously you need to take k steps.

So with that in mind, we can take advantage of this k step difference, and we define two Pointers, one fast and one slow. We first set the fast pointer to move k+1, and then set the slow pointer to point to the head node. At this point, whether the slow pointer and the fast pointer are exactly k steps apart, then let the slow pointer and the fast pointer move at the same time. When fast points to the end of the list, which is null, the slow pointer is exactly the KTH element from last.

The implementation of the relevant code is as follows:

public static ListNode findKElementFromEnd(ListNode listNode,int k){
        if (k <= 0) {return null;
        }
        ListNode fast = listNode;
        ListNode slow = listNode;

        //fast ! =null in case k is greater than the length of the list
        while(fast ! =null && k > 0) {// The fast pointer takes k steps first
            fast = fast.next;
            k--;
        }
        while (null! = fast){// The fast and slow Pointers go together until fast=null
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
Copy the code

Note that if k is greater than the length of the list, the head node will be returned. This is a detail problem, and if you are interviewing, you should ask what you should do if K is greater than the length of the list.

conclusion

This paper mainly describes the basic add, delete, change and check operation of linked list, and through simple add, delete, change and check operation, the introduction of more advanced linked list merge and linked list inversion algorithm, and finally we can get a good grasp of the linked list has three key points: The first is to prevent pointer loss, and then we can introduce sentinels to simplify the operation of linked lists. Finally, we can write a more efficient and concise linked list algorithm by cleverly using double Pointers.