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

简介: 【数据结构与算法】5.详解双向链表的基本操作(Java语言实现)


0. 前言

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

1. 双链表的定义

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

单链表的特点:

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

双链表的特点:

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

双链表的定义:

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

指针域(prev):用于指向当前节点的直接前驱节点;

数据域(data):用于存储数据元素;

指针域(next):用于指向当前节点的直接后继节点。

2. LinkedList 模拟实现

2.1 接口

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 定义双向链表类

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

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

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

2.4 头插法

  1. 判断链表是否为空,如果为空,将新节点的node设置为头节点,将新节点的node设置为尾节点
head = node;
last = node;
  1. 如果链表不为空,将新节点的nodenext域设置为头节点,将当前头节点的prev设置为新节点的node,更新头节点为新节点的node
node.next = head;
head.prev = node;
head = node;

动画演示:

代码:

/**
* 头插法
* @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 尾插法

  1. 判断链表是否为空,如果为空,将新节点的node设置为头节点,将新节点的node设置为尾节点
head = node;
last = node;
  1. 如果链表不为空,将最后一个节点lastnext域指向新节点,新节点的prev域指向最后一个节点,更新尾节点为新节点
last.next = node;
node.prev = last;
last = 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;
        }
    }

2.6 指定位置插入元素

  1. 判断索引idnex是否合法,如果不合法则抛出异常。
if (index < 0 || index > size()) {
  throw new IndexException("index不合法:" + index);
}
  1. 判断链表是否为空,如果为空则将新节点设置为头节点和尾节点
if (head == null) {
  head = node;
    last = node;
    return;
}
  1. 如果索引index == 0,则使用头插法,如果索引index = 链表长度,则使用尾插法
if (index == 0) {
    addFirst(data);
  return;
}
if (index == size()) {
    addLast(data);
  return;
}
  1. 找到索引节点(当前节点)
private ListNode findIndex(int index) {
        ListNode cur = head;
        while (index != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }
  1. 将新节点的next域指向当前节点,新节点的prev域指向当前节点的前一个节点,当前节点的prev域指向新节点,更新新节点的上一个节点的next域指向当前节点。
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.

代码:

@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域置为空。

  3. 情况二:链表中只有一个元素,且正好要删除这个元素。
  4. 情况三:删除的节点为尾节点,更新尾节点为当前节点的上一个节点,上一个节点的next域置为空

  5. 情况四:删除中间节点,当前节点的上一个节点的next域指向当前节点的下一个节点,更新下一个节点的prev域指向当前节点的上一个节点

  6. 删除了节点就结束方法的执行

代码:

@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 删除链表中所有指定元素

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

代码:

@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 统计链表元素个数

代码:

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

2.11 清空链表

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

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

2.12 打印链表

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

2.13 测试

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类:

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();
    }
}

接口:

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();
}

异常类:

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)
插入 空间不够时需要扩容 没有容量的概念
应用场景 元素高效存储 + 频繁访问 任意位置插入和删除频繁

相关文章
|
18天前
|
存储 算法 Java
Java数据结构与算法-java数据结构与算法(二)
Java数据结构与算法-java数据结构与算法
58 1
|
13天前
|
搜索推荐 Java
Java排序算法
Java排序算法
16 0
|
13天前
|
搜索推荐 Java
Java基础(快速排序算法)
Java基础(快速排序算法)
20 4
|
16天前
|
存储 算法 JavaScript
Java入门高频考查算法逻辑基础知识3-编程篇(超详细18题1.8万字参考编程实现)
解决这类问题时,建议采取下面的步骤: 理解数学原理:确保你懂得基本的数学公式和法则,这对于制定解决方案至关重要。 优化算法:了解时间复杂度和空间复杂度,并寻找优化的机会。特别注意避免不必要的重复计算。 代码实践:多编写实践代码,并确保你的代码是高效、清晰且稳健的。 错误检查和测试:要为你的代码编写测试案例,测试标准的、边缘情况以及异常输入。 进行复杂问题简化:面对复杂的问题时,先尝试简化问题,然后逐步分析和解决。 沟通和解释:在编写代码的时候清晰地沟通你的思路,不仅要写出正确的代码,还要能向面试官解释你的
32 0
|
18天前
|
XML 存储 算法
Java数据结构与算法-java数据结构与算法(五)
Java数据结构与算法-java数据结构与算法
47 0
|
24天前
|
自然语言处理 算法 搜索推荐
用计算机语言表示算法
在计算机科学中,算法是解决问题的核心步骤和方法的描述。然而,算法本身并不直接执行;它们需要被转换成计算机可以理解和执行的指令,这通常是通过编写代码来实现的。不同的计算机语言提供了不同的方式来表示和实现算法。本文将讨论如何使用计算机语言来表示算法,并通过一个具体示例来展示这个过程。
13 0
|
26天前
|
算法 搜索推荐 Java
利用java编写的项目设备调配系统代码示例(内含5种设备调配的算法)
利用java编写的项目设备调配系统代码示例(内含5种设备调配的算法)
13 1
|
28天前
|
并行计算 算法 搜索推荐
|
30天前
|
存储
【双向链表】数据结构双向链表的实现
【双向链表】数据结构双向链表的实现
|
1月前
|
存储
【数据结构】双向链表
【数据结构】双向链表