看动画学算法之:doublyLinkedList

关注

发布于: 1 小时前

简介今天我们来学习一下复杂一点的 LinkedList：doublyLinkedList。

和 LinkedList 相比，doublyLinkedList 中的节点除了 next 指向下一个节点之外，还有一个 prev 之前的一个节点。所以被称为 doublyLinkedList。 doublyLinkedList 是一个双向链表，我们可以向前或者向后遍历 list。

今天我们来学习一下 doublyLinkedList 的基本操作和概念。

doublyLinkedList 的构建和 linkedList 一样，doublyLinkedList 是由一个一个的节点构成的。而每个节点除了要存储要保存的数据之外，还需要存储下一个节点和上一个节点的引用。

doublyLinkedList 需要一个 head 节点，我们看下怎么构建：

public class DoublyLinkedList {

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

复制代码

}doublyLinkedList 的操作接下来，我们看一下 doublyLinkedList 的一些基本操作。

头部插入

头部插入的逻辑是：将新插入的节点作为新的 head 节点，并且将 newNode.next 指向原来的 head 节点。

同时需要将 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;}

复制代码

尾部插入

尾部插入的逻辑是：找到最后一个节点，将最后一个节点的 next 指向新插入的节点，并且将新插入的节点的 prev 指向最后一个节点。

//新节点插入到 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;}

复制代码

插入给定的位置

如果要在给定的位置插入节点，我们需要先找到插入位置的前一个节点，然后将前一个节点的 next 指向新节点。新节点的 prev 指向前一个节点。

同时我们需要将新节点的 next 指向下一个节点，下一个节点的 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;}

复制代码

删除指定位置的节点

删除节点的逻辑是：找到要删除节点的前一个节点，和下一个节点。前一个节点的 next 指向下一个节点，下一个节点的 prev 指向前一个节点。

//删除特定位置的节点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;    Node prev = temp.next.prev;    prev.prev = prev;}

复制代码

本文的代码地址：

learn-algorithm

本文收录于 http://www.flydean.com/algorithm-doubly-linked-list/

最通俗的解读，最深刻的干货，最简洁的教程，众多你不知道的小技巧等你来发现！

欢迎关注我的公众号:「程序那些事」,懂技术，更懂你！

发布于: 1 小时前阅读数: 4

原文链接:【http://xie.infoq.cn/article/414fbb54f62d75ffe68ec8f91】。文章转载请联系作者。

程序那些事

关注

关注公众号：程序那些事，更多精彩等着你！ 2020.06.07 加入

最通俗的解读，最深刻的干货，最简洁的教程，众多你不知道的小技巧，尽在公众号：程序那些事！

发布

暂无评论

创作场景

看动画学算法之:doublyLinkedList

程序那些事

评论