前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP最新优惠活动
返回腾讯云官网
社区首页 >专栏 >【数据结构与算法】5.详解双向链表的基本操作（Java语言实现）

【数据结构与算法】5.详解双向链表的基本操作（Java语言实现）

作者头像
爱敲代码的小杨.
发布于 2024-05-07 17:31:04
650
发布于 2024-05-07 17:31:04
举报
文章被收录于专栏：JavaJava

0. 前言

上一篇【数据结构与算法】4.自主实现单链表的增删查改 我们自主实现了单链表的操作，在Java的集合类中LinkedList底层实现是无头双向循环链表。所以今天我们模拟LinkedList的实现。

1. 双链表的定义

学习双链表之前，做个回顾。

单链表的特点：

  1. 我们可以轻松的到达下一个节点，但是回到前一节点是很难的。
  2. 只能从头遍历到尾或者从尾遍历到头（一般是从头到尾）

双链表的特点：

  1. 每次在插入或删除某个节点时, 需要处理四个节点的引用, 而不是两个. 实现起来要困难一些
  2. 相对于单向链表, 必然占用内存空间更大一些.
  3. 既可以从头遍历到尾, 又可以从尾遍历到头

双链表的定义：

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

指针域（prev）：用于指向当前节点的直接前驱节点；

数据域（data）：用于存储数据元素；

指针域（next）：用于指向当前节点的直接后继节点。

2. LinkedList 模拟实现

2.1 接口

代码语言：javascript
复制
public interface IList {
    //头插法
    public void addFirst(int data);

    //尾插法
    public void addLast(int data);

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data);

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key);

    //删除第一次出现关键字为key的节点
    public void remove(int key);

    //删除所有值为key的节点
    public void removeAllKey(int key);

    //得到单链表的长度
    public int size();

    // 清空链表
    public void clear();

    // 打印链表
    public void display();
}

2.2 定义双向链表类

代码语言：javascript
复制
static class ListNode {
	public int val; // 数值域 - 存放当前节点的值
	public ListNode next; // next域 指向下一个节点
	public ListNode prev; // prev域 指向上一个节点

	public ListNode(int val) {
		this.val = val;
	}
}

2.3 定义两个指针，分别指向头节点和尾节点

代码语言：javascript
复制
// 链表的属性 链表的头节点
public ListNode head; 
// 链表的属性 链表的尾节点
public ListNode last;

2.4 头插法

判断链表是否为空，如果为空，将新节点的node设置为头节点，将新节点的node设置为尾节点

代码语言：javascript
复制
head = node;
last = node;

如果链表不为空，将新节点的node的next域设置为头节点，将当前头节点的prev设置为新节点的node，更新头节点为新节点的node

代码语言：javascript
复制
node.next = head;
head.prev = node;
head = node;

动画演示：

代码：

代码语言：javascript
复制
/**
* 头插法
* @param data
*/
@Override
public void addFirst(int data) {
	ListNode node = new ListNode(data);
	if (head == null) {
		head = node;
		last = node;
	}else {
		node.next = head;
		head.prev = node;
		head = node;
	}
}

2.5 尾插法

判断链表是否为空，如果为空，将新节点的node设置为头节点，将新节点的node设置为尾节点

代码语言：javascript
复制
head = node;
last = node;

如果链表不为空，将最后一个节点last的next域指向新节点，新节点的prev域指向最后一个节点，更新尾节点为新节点

代码语言：javascript
复制
last.next = node;
node.prev = last;
last = node;

动画演示：

代码：

代码语言：javascript
复制
    /***
     * 尾插法
     * @param data
     */
    @Override
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if (head == null) {
            head = node;
            last = node;
        } else {
            last.next = node;
            node.prev = last;
            last = node;
        }
    }

2.6 指定位置插入元素

判断索引idnex是否合法，如果不合法则抛出异常。

代码语言：javascript
复制
if (index < 0 || index > size()) {
	throw new IndexException("index不合法：" + index);
}

判断链表是否为空，如果为空则将新节点设置为头节点和尾节点

代码语言：javascript
复制
if (head == null) {
	head = node;
    last = node;
    return;
}

如果索引index == 0，则使用头插法，如果索引index = 链表长度，则使用尾插法

代码语言：javascript
复制
if (index == 0) {
    addFirst(data);
	return;
}
if (index == size()) {
    addLast(data);
	return;
}

找到索引节点（当前节点）

代码语言：javascript
复制
    private ListNode findIndex(int index) {
        ListNode cur = head;
        while (index != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

将新节点的next域指向当前节点，新节点的prev域指向当前节点的前一个节点，当前节点的prev域指向新节点，更新新节点的上一个节点的next域指向当前节点。

代码语言：javascript
复制
ListNode cur = findIndex(index);
node.next = cur;
node.prev = cur.prev;
cur.prev = node;
node.prev.next = node;

动画演示：

2.7 查找指定元素

  1. 从头节点开始遍历链表，如果当前节点的值与要查找的key相等，则返回ture，如果不相等则移动下一个节点继续查找。如果遍历完链表都没有找到key则返回false.

代码：

代码语言：javascript
复制
    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

2.8 删除指定元素

  1. 从头节点开始遍历链表，找到要删除的节点
  2. 情况一：删除的节点为头节点，更新头节点为下一个节点，更新下一个节点的prev域置为空。
  1. 情况二：链表中只有一个元素，且正好要删除这个元素。
  2. 情况三：删除的节点为尾节点，更新尾节点为当前节点的上一个节点，上一个节点的next域置为空
  1. 情况四：删除中间节点，当前节点的上一个节点的next域指向当前节点的下一个节点，更新下一个节点的prev域指向当前节点的上一个节点
  1. 删除了节点就结束方法的执行

代码：

代码语言：javascript
复制
    @Override
    public void remove(int key) {
         ListNode cur = head;
         while (cur != null) {
             if (cur.val == key) { // 找到要删除的元素了
                 if (cur == head) { // 删除头节点
                     head = head.next;
                     if (head != null) {
                         head.prev = null;
                     } else { // 链表中只有一个元素，且这个正好删除这个元素
                         last = null;
                     }
                 } else { // 删除中间节点
                     cur.prev.next = cur.next;
                     if (cur.next != null) {
                        cur.next.prev = cur.prev;
                     } else {
                         // 删除尾节点
                         last = cur.prev;
                     }
                 }
                 return;// 删除了节点就结束方法
             }
             cur = cur.next;
         }
    }

2.9 删除链表中所有指定元素

从头节点遍历链表，与删除指定元素的方式一样，删除节点后继续遍历链表，直到遍历完链表，删除所有指定的元素即可。

代码：

代码语言：javascript
复制
    @Override
    public void removeAllKey(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) { // 找到要删除的元素了
                if (cur == head) { // 删除头节点
                    head = head.next;
                    if (head != null) {
                        head.prev = null;
                    } else { // 链表中只有一个元素，且这个正好删除这个元素
                        last = null;
                    }
                } else { // 删除中间节点
                    cur.prev.next = cur.next;
                    if (cur.next != null) {
                        cur.next.prev = cur.prev;
                    } else {
                        // 删除尾节点
                        last = cur.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }

2.10 统计链表元素个数

代码：

代码语言：javascript
复制
    @Override
    public int size() {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

2.11 清空链表

将头节点和尾节点置为空，没有引用指向直接被JVM回收

代码语言：javascript
复制
    @Override
    public void clear() {
        head = null;
        last = null;
    }

2.12 打印链表

代码语言：javascript
复制
    @Override
    public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

2.13 测试

代码语言：javascript
复制
public class Test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        // 头插法
        myLinkedList.addFirst(1);
        myLinkedList.addFirst(2);
        myLinkedList.addFirst(3);
        // 打印链表
        myLinkedList.display();

        System.out.println("=========");

        // 尾插法
        myLinkedList.addLast(4);
        myLinkedList.addLast(5);
        myLinkedList.addLast(6);
        // 打印链表
        myLinkedList.display();

        System.out.println("=========");

        // 在4 位置插入7
        myLinkedList.addIndex(4,7);
        // 打印链表
        myLinkedList.display();

        System.out.println("=========");

        // 查找元素 7 8
        System.out.println(myLinkedList.contains(7));
        System.out.println(myLinkedList.contains(8));

        System.out.println("=========");

        // 删除3 6 4
        myLinkedList.remove(3);
        myLinkedList.display();
        System.out.println("=========");

        myLinkedList.remove(6);
        myLinkedList.display();
        System.out.println("=========");

        myLinkedList.remove(4);
        myLinkedList.display();
        System.out.println("=========");


        // 删除全部的2
        myLinkedList.addLast(2);
        myLinkedList.addLast(2);
        myLinkedList.addLast(2);
        myLinkedList.display();
        myLinkedList.removeAllKey(2);
        myLinkedList.display();

        System.out.println("=========");

        // 统计个数
        System.out.println(myLinkedList.size());

        System.out.println("=========");

        // 清空链表
        myLinkedList.clear();
        myLinkedList.display();
        System.out.println("=========");
        
        // 统计个数
        System.out.println(myLinkedList.size());
    }
}

// 运行结果
3 2 1 
=========
3 2 1 4 5 6 
=========
3 2 1 4 7 5 6 
=========
true
false
=========
2 1 4 7 5 6 
=========
2 1 4 7 5 
=========
2 1 7 5 
=========
2 1 7 5 2 2 2 
1 7 5 
=========
3
=========

=========
0

3.代码

MyLinkedList类：

代码语言：javascript
复制
public class MyLinkedList implements IList{

    static class ListNode {
        public int val; // 数值域 - 存放当前节点的值
        public ListNode next; // next域 指向下一个节点
        public ListNode prev; // prev域 指向上一个节点

        public ListNode(int val) {
            this.val = val;
        }
    }

    // 链表的属性 链表的头节点
    public ListNode head;
    // 链表的属性 链表的尾节点
    public ListNode last;

    /**
     * 头插法
     * @param data
     */
    @Override
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        if (head == null) {
            head = node;
            last = node;
        }else {
            node.next = head;
            head.prev = node;
            head = node;
        }
    }

    /***
     * 尾插法
     * @param data
     */
    @Override
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if (head == null) {
            head = node;
            last = node;
        } else {
            last.next = node;
            node.prev = last;
            last = node;
        }
    }

    @Override
    public void addIndex(int index, int data) {
        if (index < 0 || index > size()) {
            throw new IndexException("index不合法：" + index);
        }
        ListNode node = new ListNode(data);
        if (head == null) {
            head = node;
            last = node;
            return;
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }
        ListNode cur = findIndex(index);
        node.next = cur;
        node.prev = cur.prev;
        cur.prev = node;
        node.prev.next = node;
    }

    private ListNode findIndex(int index) {
        ListNode cur = head;
        while (index != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
         ListNode cur = head;
         while (cur != null) {
             if (cur.val == key) { // 找到要删除的元素了
                 if (cur == head) { // 删除头节点
                     head = head.next;
                     if (head != null) {
                         head.prev = null;
                     } else { // 链表中只有一个元素，且这个正好删除这个元素
                         last = null;
                     }
                 } else { // 删除中间节点
                     cur.prev.next = cur.next;
                     if (cur.next != null) {
                        cur.next.prev = cur.prev;
                     } else {
                         // 删除尾节点
                         last = cur.prev;
                     }
                 }
                 return;
             }
             cur = cur.next;
         }
    }

    @Override
    public void removeAllKey(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) { // 找到要删除的元素了
                if (cur == head) { // 删除头节点
                    head = head.next;
                    if (head != null) {
                        head.prev = null;
                    } else { // 链表中只有一个元素，且这个正好删除这个元素
                        last = null;
                    }
                } else { // 删除中间节点
                    cur.prev.next = cur.next;
                    if (cur.next != null) {
                        cur.next.prev = cur.prev;
                    } else {
                        // 删除尾节点
                        last = cur.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }

    @Override
    public int size() {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    @Override
    public void clear() {
        head = null;
        last = null;
    }

    @Override
    public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}

接口：

代码语言：javascript
复制
public interface IList {
    //头插法
    public void addFirst(int data);

    //尾插法
    public void addLast(int data);

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data);

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key);

    //删除第一次出现关键字为key的节点
    public void remove(int key);

    //删除所有值为key的节点
    public void removeAllKey(int key);

    //得到单链表的长度
    public int size();

    // 清空链表
    public void clear();

    // 打印链表
    public void display();
}

异常类：

代码语言：javascript
复制
public class IndexException extends RuntimeException{
    public IndexException() {

    }
    public IndexException(String msg) {
        super(msg);
    }
}

4. ArrayList和LinkedList的区别

不同点

ArrayList

LinkedList

存储空间上

物理上一定连续

逻辑上连续，但物理上不一定连续

随机访问

支持O(1)

不支持O(n)

头插

需要搬移元素，效率低O(n)

只需要修改引用的指向，时间复杂度为O(1)

插入

空间不够时需要扩容

没有容量的概念

应用场景

元素高效存储 + 频繁访问

任意位置插入和删除频繁

?

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2024-02-02，如有侵权请联系 cloudcommunity@tencent.com 删除
public
遍历
链表
数据结构与算法
java

本文分享自 作者个人站点/博客?前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与?腾讯云自媒体分享计划? ，欢迎热爱写作的你一起参与！

public
遍历
链表
数据结构与算法
java
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
LV.
文章
0
获赞
0
目录
  • 0. 前言
  • 1. 双链表的定义
  • 2. LinkedList 模拟实现
    • 2.1 接口
      • 2.2 定义双向链表类
        • 2.3 定义两个指针，分别指向头节点和尾节点
          • 2.4 头插法
            • 2.5 尾插法
              • 2.6 指定位置插入元素
                • 2.7 查找指定元素
                  • 2.8 删除指定元素
                    • 2.9 删除链表中所有指定元素
                      • 2.10 统计链表元素个数
                        • 2.11 清空链表
                          • 2.12 打印链表
                            • 2.13 测试
                            • 3.代码
                            • 4. ArrayList和LinkedList的区别
                            领券

                            腾讯云开发者

                            扫码关注腾讯云开发者

                            扫码关注腾讯云开发者

                            领取腾讯云代金券

                            热门产品

                            热门推荐

                            更多推荐

                            Copyright ? 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有?

                            深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059?深公网安备号 44030502008569

                            腾讯云计算（北京）有限责任公司 京ICP证150476号 | ?京ICP备11018762号 | 京公网安备号11010802020287

                            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

                            Copyright ? 2013 - 2024 Tencent Cloud.

                            All Rights Reserved. 腾讯云 版权所有

                            登录 后参与评论
                            http://www.vxiaotou.com