Мало знаний, большой вызов! Эта статья участвует в "Необходимые знания для программистов«Творческая деятельность

Введение

Сегодня мы узнаем о более сложном LinkedList: doubleLinkedList.

По сравнению с LinkedList узлы в doubleLinkedList не только указывают на следующий узел, но также имеют узел перед предыдущим. Так называемый дважды связанный список. doubleLinkedList — это двусвязный список, мы можем перемещаться по списку вперед или назад.

Сегодня давайте изучим основные операции и концепции doubleLinkedList.

Построение дважды связанного списка

Как и linkedList, doubleLinkedList состоит из узлов один за другим. В дополнение к хранению данных, которые необходимо сохранить, каждый узел также должен хранить ссылку на следующий узел и предыдущий узел.

doubleLinkedList нуждается в головном узле, давайте посмотрим, как его построить:

public class DoublyLinkedList {

    Node head; // head 节点

    //Node表示的是Linked list中的节点，包含一个data数据，上一个节点和下一个节点的引用
    class Node {
        int data;
        Node next;
        Node prev;
        //Node的构造函数
        Node(int d) {
            data = d;
        }
    }
}

Операция doubleLinkedList

Далее давайте рассмотрим некоторые основные операции doubleLinkedList.

вставка головы

Логика вставки головы такова: возьмите вновь вставленный узел в качестве нового головного узла и укажите newNode.next на исходный головной узел.

Также необходимо указать head.prev на новый узел вставки.

Взгляните на код Java:

    //插入到linkedList的头部
    public void push(int newData) {
        //构建要插入的节点
        Node newNode = new Node(newData);
        //新节点的next指向现在的head节点
        //新节点的prev指向null
        newNode.next = head;
        newNode.prev = null;

        if (head != null)
            head.prev = newNode;

        //现有的head节点指向新的节点
        head = newNode;
    }

вставка хвоста

Логика вставки хвоста такова: найти последний узел, указать следующий из последних узлов на вновь вставленный узел и указать предыдущий узел вновь вставленного узла на последний узел.

   //新节点插入到list最后面
    public void append(int newData) {
        //创建新节点
        Node newNode = new Node(newData);
        //如果list是空，则新节点作为head节点
        if (head == null) {
            newNode.prev = null;
            head = newNode;
            return;
        }

        newNode.next = null;
        //找到最后一个节点
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        //插入
        last.next = newNode;
        newNode.prev = last;
        return;
    }

вставить в указанную позицию

Если мы хотим вставить узел в заданную позицию, нам нужно сначала найти предыдущий узел в позиции вставки, а затем указать следующий узел предыдущего узла на новый узел. Prev нового узла указывает на предыдущий узел.

В то же время нам нужно указать следующий узел нового узла на следующий узел, а предыдущий узел следующего узла указать на новый узел.

    //插入在第几个元素之后
    public void insertAfter(int index, int newData) {
        Node prevNode = head;
        for (int i = 1; i < index; i++) {
            if (prevNode == null) {
                System.out.println("输入的index有误，请重新输入");
                return;
            }
            prevNode = prevNode.next;
        }
        //创建新的节点
        Node newNode = new Node(newData);
        //新节点的next指向prevNode的下一个节点
        newNode.next = prevNode.next;
        //将新节点插入在prevNode之后
        prevNode.next = newNode;
        //将新节点的prev指向prevNode
        newNode.prev = prevNode;

        //newNode的下一个节点的prev指向newNode
        if (newNode.next != null)
            newNode.next.prev = newNode;
    }

удалить узел в указанной позиции

Логика удаления узла такова: найти предыдущий узел и следующий узел узла, который нужно удалить. Следующий узел предыдущего узла указывает на следующий узел, а предыдущий узел следующего узла указывает на предыдущий узел.

    //删除特定位置的节点
    void deleteNode(int index)
    {
        // 如果是空的，直接返回
        if (head == null)
            return;

        // head节点
        Node temp = head;

        // 如果是删除head节点
        if (index == 1)
        {
            head = temp.next;
            return;
        }

        // 找到要删除节点的前一个节点
        for (int i=1; temp!=null && i<index-1; i++)
            temp = temp.next;

        // 如果超出范围
        if (temp == null || temp.next == null)
            return;

        // temp->next 是要删除的节点，删除节点
        Node next = temp.next.next;
        temp.next = next;
        next.prev=temp;
    }

Кодовый адрес этой статьи:

learn-algorithm

Эта статья включена вWoohoo. Floyd Press.com/algorithm-of…

Самая популярная интерпретация, самая глубокая галантерея, самые краткие уроки и множество трюков, о которых вы не знаете, ждут вас!

Добро пожаловать, чтобы обратить внимание на мой официальный аккаунт: «Программируйте эти вещи», разбирайтесь в технологиях, лучше поймите себя!