| 一步步带你用Java实现双向链表（超详细） | 您所在的位置：网站首页 › 什么叫双向链表 › 一步步带你用Java实现双向链表（超详细） |
一步步带你用Java实现双向链表（超详细）
|
@[toc] 上一节说到了单链表,这一节我们来手写一个双向链表，在这之前，需要先补充一下关于双链表的概念。 什么是双向链表双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
存储的数据 T data、直接前驱节点 Node pri、直接后继节点 Node next private static class Node { private T data; private Node pri; private Node next; } size链表中节点的数量 数据插入 头插法 addFirst(T value)插入数据首先要对链表进行判空 如果链表为空 头结点 = 插入的节点 = 尾结点 不为空则: 1、将插入节点的next指向头结点 2、调整头结点的前驱为新节点 3、将新节点设置为头结点 4、size++ 实现细节： Node node = new Node(value); if (size == 0) { first = node; last = first; }else { node.next = first; first.pri = node; first = node; } size++; 尾插法 addLast(T value)依旧要对链表进行判空 为空时： 等价于头插，直接调用addFirst 不为空： 1、调整尾结点的后继next指向新节点 2、调整新节点的前驱pri指向尾结点 3、更新尾结点为新的节点 4、size++ 实现细节 if (size == 0){ return addFirst(value); }else { Node node = new Node(value); last.next = node; node.pri = last; last = node; } size++; 插入到指定下标位置add(int index)由于是根据下标插入的，所以首先要判断下标 注意，此时的下标最大值应该是size-1，但是在插入的时候是==可以取到size的==，因为此时的下标代表的是==插入的位置==（注意和删除时进行区分） 下标不合法: 这里我选择了抛出异常，也可以进行其他处理 下标合法【0 - size】： 1、判断下标取值 为0 即进行头插法 addFirst(T value) 为size 即进行尾插法 addLast(T value) 为其他值： 遍历到指定节点的前一个节点-> left 设置新节点的next值为left的next值 将left的next值设置为新节点 调整新节点的pri值为left 调整新节点的next节点的pri值为新节点 2、size++ 实现细节 add(int index,T value){ if (index size-1){ throw new IndexOutOfBoundsException("数据下标越界 Index:" + index + "\tsize:" + size); } else if(index == 0){ return addFirst(value); }else if (index == size){ return addLast(value); }else { Node node = new Node(value); Node head = first; for (int i = 0; i |
【本文地址】
公司简介
联系我们