4.双向链表
双向链表
- 单向链表只能通过Node中的next属性(指针)从头遍历链表，完成搜素
- 双向链表中的Node增加perv属性，指向该节点的上一个节点
- 双向链表查找元素可以从first或last两个方向开始查找
双向链表的接口设计
- 相较于单向链表的构造器：需要在构造器中将prev属性放入，同时在初始类时，需要指明一个私有的last节点
- 相较于单向链表的方法：需要重写add，remove，node(查找节点)，clear四个方法
双向链表的实现
public class LinkedList {private int size; //用来记录链表长度private Node first; //用来指向初始数据private Node last;//私有类，用来记录链表中的节点private static class Node {E element; //Node类中属性1：用来记录数据Node next; //Node类中属性2：用来记录指针指向下一个元素Node prev; //Node类中属性3：用来记录指针指向前一个元素//构造方法public Node(Node prev, E element, Node next) {this.element = element;this.next = next;this.prev = prev;}}/*** 一、查找元素* 通过判断索引在链表的前后判断进行分类*///通过判断索引在链表的前后判断进行分类public Node node(int index) {//判断索引是否越界rangeCheck(index);//在链表前半部分if (index < (size >> 1)) {Node node = first;for (int i = 0; i < index; i++) {node = node.next;}return node;}else {//在链表后半部分Node node = last;for (int i = size - 1; i > index ; i--) {node = node.prev;}return node;}}/*** 二、添加元素* 在中间部分插入元素* 1. 首先找到索引元素：Node next = node(index);* 2. 找到索引元素的前面元素：Node prev = next.prev;* 3. 通过Node node = new Node<>(prev, element, next);来实现新元素的prev与next指针的指向* 4. 通过prev.next = node;与next.prev = node;来实现原先元素指针的指向* 在头部添加元素* 见代码实现* 在尾部添加元素* 见代码实现*/public void add(int index, E element) {//检查索引是否越界rangeCheckForAdd(index);//这是链表添加的第一个元素或者末尾元素if (index == size) {Node oldLast = last;last = new Node<>(oldLast, element, null);if (oldLast == null) {//链表添加的第一个元素first = last;} else {//链表向末尾添加元素oldLast.next = last;}} else {//链表向中间添加元素或者向头部添加元素Node next = node(index);Node prev = next.prev;Node node = new Node<>(prev, element, next);next.prev = node;if (prev == null) {//链表向初始添加元素first = node;} else {//链表向中间添加元素prev.next = null;}}size++;}/*** 三、删除元素* 删除节点：只需让被删节点的前后节点进行连接* 同时：需要处理第一个节点和最后一个节点*/public E remove(int index) {//检查索引是否越界rangeCheck(index);// 需要删除的节点Node node = node(index);// 删除节点的前一个节点Node prev = node.prev;// 删除节点的后一个节点Node next = node.next;// 删除节点, 只需要去掉对这个节点的引用即可// 如果prev == null, 说明删除的是第一个节点if (prev == null) {first = next;}else {prev.next = next;}// 如果next == null, 说明删除的是最后一个节点if (next == null) {last = prev;}else {next.prev = prev;}size--;return node.element;}/*** 四、清空元素* 清空元素只需讲first指向null，同时size设为0即可*/public void clear() {first = null;last = null;size = 0;}}
双向链表与动态数组
-
动态数组：开辟、销毁内存空间的次数相对较少，但可能造成内存空间浪费(通过缩容解决)
-
双向链表：开辟、销毁内存空间的次数相对较多，但不会造成内存空间浪费
-
如果频繁在尾部进行添加、删除操作，动态数组与双向链表均可
-
如果频繁在头部进行添加、删除操作，建议使用双向链表
-
如果有频繁的在任意位置的添加、删除操作，建议使用双向链表
-
如果有频繁的查询操作(随机访问操作)，建议使用动态数组
-
以上操作考虑时间复杂度(最好复杂度，平均复杂度，最好复杂度同时使用)
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！