Bidirectional linked list and bidirectional circular linked list

Introduction to bidirectional linked list

The unidirectional linked list has only one direction, and the node has only one subsequent pointer. Next points to the following node. The two-way linked list, as its name suggests, supports two directions. Each node has more than one subsequent pointer next pointing to the following node, and a precursor pointer prev pointing to the previous node.

As can be seen from the above figure, the two-way linked list needs two additional spaces to store the addresses of subsequent nodes and predecessor nodes. Therefore, if the same amount of data is stored, the two-way linked list will occupy more memory space than the single linked list. Although two pointers waste storage space, they can support two-way traversal, which also brings the flexibility of two-way linked list operation. Compared with single linked list, what kind of problem is bidirectional linked list suitable for?

Structurally, the two-way linked list can support finding the precursor node in the case of O(1) time complexity. It is this feature that also makes the insertion, deletion and other operations of the two-way linked list simpler and more efficient than the single linked list in some cases.

Add, delete, change and query operations of two-way linked list

1. Insert operation

  • Head insertion: time complexity O(1)
  • Tail insertion: time complexity O(1)
  • Insert after specified location: time complexity O(1)
  • Insert before the specified position: time complexity O(1) -- pay attention to the difference between one-way linked list and one-way linked list

2. Delete

The time complexity of the delete operation is similar to that of the insert operation.

  • Delete header node: time complexity O(1)
  • Delete tail node: time complexity O(1)
  • Delete nodes with a value equal to a certain number: time complexity O(n)
  • Delete a specific node: O(1)

The deletion operation is explained here.

In actual software development, deleting a data from the linked list is no different from these two situations:

  1. Delete the node with "value equal to a given value" in the node;

  2. Delete the node pointed to by the given pointer.

For the first case, whether it is a single linked list or a two-way linked list, in order to find the node whose value is equal to the given value, we need to traverse and compare one by one from the first node until we find the node whose value is equal to the given value, and then delete it through the pointer operation I mentioned earlier.

Although the time complexity of simple deletion operation is O(1), the time of traversal search is the main time-consuming point, and the corresponding time complexity is O(n). According to the addition rule in time complexity analysis, the total time complexity of the linked list operation corresponding to the node whose deletion value is equal to the given value is O(n).

For the second case, we have found the node to be deleted, but to delete a node Q, we need to know its precursor node, and the single linked list does not support direct access to the precursor node. Therefore, in order to find the precursor node, we still have to traverse the linked list from the first node until p - > next = q, indicating that P is the precursor node of Q.

But for the two-way linked list, this situation has advantages. Because the node in the bidirectional linked list has saved the pointer of the precursor node, it does not need to traverse like the single linked list. Therefore, for the second case, the single linked list deletion operation needs O(n) time complexity, while the two-way linked list only needs to be completed within O(1) time complexity!

In addition to the advantages of insert and delete operations, for an ordered linked list, the efficiency of value-based query of two-way linked list is also higher than that of single linked list. Because we can record the location p of the last search. During each query, we decide whether to search forward or backward according to the relationship between the value to be searched and the size of p, so we only need to search half of the data on average.

Now, do you think a two-way linked list is more efficient than a single linked list? This is why in the actual software development, although the two-way linked list costs more memory, it is still more widely used than the single linked list. If you are familiar with the Java language, you must have used the LinkedHashMap container. If you deeply study the implementation principle of LinkedHashMap, you will find that the data structure of two-way linked list is used.

3. Update operation

  • Update specified node: time complexity O(1)
  • Update the node whose value in the linked list is equal to a specific value: time complexity O(n)

4. Query operation

  • Time complexity: O(n)

Java code implementation of bidirectional linked list

public class TwoWayLinkedList<E> {


    public static void main(String[] args) {
        TwoWayLinkedList<Integer> list = new TwoWayLinkedList<>();
        //Tail insertion, traversal linked list output
        System.out.println("Tail insertion[1-10]");
        for (int i = 1; i <= 10; i++) {
            list.addLast(Integer.valueOf(i));
        }
        list.printList();
        //Insert the header and traverse the linked list output
        System.out.println("Head insertion[1-10]");
        for (int i = 1; i <= 10; i++) {
            list.addFirst(Integer.valueOf(i));
        }
        list.printList();
        //Insert after the specified node
        System.out.println("Insert after header node[100]");
        list.addAfter(100, list.head);
        list.printList();
        System.out.println("Insert before header node[100]");
        list.addBefore(100, list.head);
        list.printList();
        System.out.println("Insert before tail node[100]");
        list.addBefore(100, list.tail);
        list.printList();
        System.out.println("Insert after tail node[100]");
        list.addAfter(100, list.tail);
        list.printList();

        System.out.println("------------Delete method test-----------");
        System.out.println("Delete header node");
        list.removeFirst();
        list.printList();
        System.out.println("Delete tail node");
        list.removeLast();
        list.printList();
        System.out.println("Delete the specified node");
        list.removeNode(list.head.next);
        list.printList();
    }


    private Node head;
    private Node tail;

    public TwoWayLinkedList() {
    }

    public TwoWayLinkedList(E data) {
        Node node = new Node<>(data, null,null);
        head = node;
        tail = node;
    }

    public void printList() {
        Node p = head;
        while (p != null && p.next != null) {
            System.out.print(p.data + "-->");
            p = p.next;
        }
        if (p != null) {
            System.out.println(p.data);
        }
    }

    public void addFirst(E data) {
        Node newNode = new Node(data,null ,head);
        if(head!=null){
            head.pre = newNode;
        }
        head = newNode;
        if (tail == null) {
            tail = newNode;
        }
    }

    public void addLast(E data) {
        Node newNode = new Node(data, tail,null);
        if (tail == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
    }

    /**
     * @param data
     * @param node node The node must be in the linked list
     */
    public void addAfter(E data, Node node) {
        if (node == null) {
            return;
        }
        Node newNode = new Node(data, node,node.next);
        if(node.next!=null){
            node.next.pre = newNode;
        }
        node.next = newNode;
        if (tail == node) {
            tail = newNode;
        }
    }

    public void addBefore(E data, Node node) {
        if (node == null) {
            return;
        }
        if(node==head){
            addFirst(data);
        }else {
            Node newNode = new Node(data,node.pre,node);
            node.pre.next = newNode;
            node.pre = newNode;
        }
    }

    public void removeFirst() {
        if (head == null) {
            return;
        }
        if (head == tail) {
            head = null;
            tail = null;
        } else {
            if(head.next!=null){
                head.next.pre = null;
            }
            head = head.next;
        }
    }

    public void removeLast() {
        if (tail == null) {
            return;
        }
        if (head == tail) {
            head = null;
            tail = null;
        } else {
            if(tail.pre!=null){
                tail.pre.next = null;
                Node p = tail.pre;
                tail.pre = null;
                tail = p;
            }
        }
    }

    public void removeNode(Node node) {
        if (node == null) {
            return;
        }
        if(node==head){
            removeFirst();
        }
        if(node==tail){
            removeLast();
        }
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    private static class Node<E> {
        E data;
        Node pre;
        Node next;

        public Node(E data, Node pre, Node next) {
            this.data = data;
            this.pre = pre;
            this.next = next;
        }
    }

}

JDK implementation of bidirectional linked list

The LinkedList in JDK is a bidirectional linked list. We can use it directly or make simple packaging.

package com.csx.algorithm.link;

import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Set;
import java.util.function.Predicate;

public class SinglyLinkedList2<E> {

    private LinkedList<E> list;

    public SinglyLinkedList2() {
        this.list = new LinkedList<>();
    }

    public SinglyLinkedList2(E data){
        Set<E> singleton = Collections.singleton(data);
        this.list = new LinkedList<>(singleton);
    }

    public SinglyLinkedList2(Collection<? extends E> c){
        this.list = new LinkedList<>(c);
    }

    // ----------------------------------New method---------------------------------------

    public void addFirst(E data){
        list.addFirst(data);
    }

    public void addLast(E data){
        list.addLast(data);
    }
    // Add at the end of the linked list
    public boolean add(E date){
        return list.add(date);
    }

    public boolean addAll(Collection<? extends E> collection){
        return list.addAll(collection);
    }

    public boolean addBefore(E data,E succ){
        int i = list.indexOf(succ);
        if(i<0){
            return false;
        }
        list.add(i,data);
        return true;
    }

    public boolean addAfter(E data,E succ){
        int i = list.indexOf(succ);
        if(i<0){
            return false;
        }
        if((i+1)==list.size()){
            list.addLast(data);
            return true;
        }else {
            list.add(i+1,data);
            return true;
        }
    }
    // ----------------------------------Delete method---------------------------------------
    // Delete method: delete the head element of the linked list by default
    public E remove(){
        return list.remove();
    }
    // Delete method: delete the first element of the linked list
    public E removeFirst(){
        return list.removeFirst();
    }
    // Delete method to delete the last element of the linked list
    public E removeLast(){
        return list.removeLast();
    }
    // Delete the element that appears for the first time in the linked list, and return true after successful deletion
    // The criterion for object equality is to call the equals method
    public boolean remove(E data){
        return list.remove(data);
    }
    // The logic is the same as the remove (E data) method
    public boolean removeFirstOccur(E data){
        return list.removeFirstOccurrence(data);
    }
    // Because the LinkedList is a two-way linked list, the time complexity is the same as removefirstoccurs
    public boolean removeLastOccur(E data){
        return list.removeLastOccurrence(data);
    }
    // Batch deletion method
    public boolean removeAll(Collection<?> collection){
        return list.removeAll(collection);
    }
    // Delete by condition
    public boolean re(Predicate<? super E> filter){
        return list.removeIf(filter);
    }
    // -----------------------------Query method----------------------------
    // Query linked list header element
    public E getFirst(){
        return list.getFirst();
    }
    // Query tail elements of linked list
    public E getLast(){
        return list.getLast();
    }
    // Query whether the linked list contains an element
    // Support null judgment
    // The criterion for equality is data equals(item)
    public boolean contains(E data){
        return list.contains(data);
    }
    public boolean containsAll(Collection<?> var){
        return list.containsAll(var);
    }

}

As a reminder, LinkedList is not thread safe. If you need to ensure thread safety, you need to do synchronization control yourself.

Bidirectional circular linked list

In fact, it is to point the leading pointer of the head node to the tail node and the trailing pointer of the tail node to the head node.

Comparison of arrays and linked lists

However, the comparison between arrays and linked lists cannot be limited to time complexity. Only the complexity of the data stored in the software development can not be used to determine the actual data structure.

The array is simple and easy to use. It uses continuous memory space in the implementation. The data in the array can be read in advance with the help of the CPU cache mechanism, so the access efficiency is higher. The linked list is not stored continuously in memory, so it is not friendly to CPU cache and can not be read effectively.

The disadvantage of array is that its size is fixed. Once declared, it will occupy the whole block of continuous memory space. If the declared array is too large, the system may not have enough continuous memory space allocated to it, resulting in "out of memory". If the declared array is too small, it may not be enough. At this time, you can only apply for a larger memory space to copy the original array, which is very time-consuming. The linked list itself has no size limit and naturally supports dynamic capacity expansion. I think this is also the biggest difference between it and array.

In addition, if your code is very demanding on the use of memory, the array is more suitable for you. Because each node in the linked list needs to consume additional storage space to store a pointer to the next node, the memory consumption will double. Moreover, frequent insertion and deletion of linked lists will also lead to frequent memory application and release, which is easy to cause memory fragmentation. If it is Java language, it may lead to frequent GC (Garbage Collection). Therefore, in our actual development, for different types of projects, we should weigh whether to choose array or linked list according to the specific situation.

Tags: linked list

Posted by ltd on Wed, 04 May 2022 01:05:22 +0300