但行好事  莫问前程

自己实现集合框架(八):双链表的实现

这是系列文章,每篇文章末尾均附有源代码地址。目的是通过模拟集合框架的简单实现,从而对常用的数据结构和java集合有个大概的了解。当然实现没有java集合的实现那么复杂,功能也没有那么强大,但是可以通过这些简单的实现窥探到底层的一些共性原理。

一. 双链表的数据结构

双链表是针对于单链表而言的,我们知道,单链表的每个节点有两个域,一个是数据域,存储元素结点的数据,一个是next链域,存储该结点后继元素的地址。而双链表的每个结点有三个域,一个数据域,存储元素结点的数据,两个链域,分别指向它的前驱结点和后继结点,单个结点结构示意图如下所示:

双链表的结构如下图所示:

单链表中,每个结点只有一个指向其后继结点的链。如果要查找某个结点的前驱结点,需要从链表的头结点开始沿着链表方向逐个遍历,操作效率很低,所以这个时候我们需要使用双链表。

二.双链表的实现

双链表比单链表在结点的数据结构上增加一个指向前驱结点的链,使得某个结点能够直接获取它的前驱结点和后继结点,双链表能够沿着前后两个方向进行遍历,这给链表的操作带来了很大的便利。双链表判断是否为空,遍历等操作和单链表比较类似,下面不再重复讨论,可以参考前面的文章自己实现集合框架(四):单链表的实现,下面主要讨论双链表的插入和删除操作。

1.定义双链表节点类

双链表节点类DoubleLinkNode的定义如下所示:

package org.light4j.dataStructure.linearList.linkList.doubleLink;

/**
 * 双链表结点类
 * 
 * @author longjiazuo
 */
public class DoubleLinkNode<E> {
    public E data;// 数据元素
    public DoubleLinkNode<E> prev;// 前驱结点
    public DoubleLinkNode<E> next;// 后继结点

    /**
     * 指定数据元素,前驱结点和后继结点的构造函数
     * 
     * @param data
     * @param prev
     * @param next
     */
    public DoubleLinkNode(E data, DoubleLinkNode<E> prev, DoubleLinkNode<E> next) {
        this.data = data;
        this.prev = prev;
        this.next = next;
    }

    /**
     * 指定数据元素的构造函数
     * 
     * @param data
     */
    public DoubleLinkNode(E data) {
        this(data, null, null);
    }

    /**
     * 默认构造函数
     */
    public DoubleLinkNode() {
    }
}

代码解释:

成员变量data保存当前结点的数据元素,prev指向前驱结点,next指向后继结点。

2.定义双链表类

双链表类DoubleLinkedList的定义如下,head成员变量表示双链表的头结点。

package org.light4j.dataStructure.linearList.linkList.doubleLink;

import org.light4j.dataStructure.linearList.LList;

/**
 * 双链表类
 * 
 * @author longjiazuo
 */
public class DoubleLinkedList<E> implements LList<E> {
    protected DoubleLinkNode<E> head;// 双链表的头结点
    protected int n;// 双链表的长度

    public DoubleLinkedList() {// 构造空双链表
        this.head = new DoubleLinkNode<E>(null, null, null);// 头指针
        this.n = 0;
    }
}

代码解释:

双链表DoubleLinkedList类实现接口LList,所以必须实现该接口的相关方法,具体实现在下面讲解。

3. 双链表的插入

对双链表进行插入操作非常方便,只需要改变节点间的链接关系即可,不需要移动元素。代码如下:

       /**
     * 在指定位置插入非空的结点
     */
    @Override
    public boolean add(int index, E element) {
        if (index < 0 || element == null) {// 如果插入序号不正确或者元素为空返回false
            return false;
        }
        if (index > this.n) {// 尾插入,把元素插入到最后面
            this.add(element);
        } else {
            DoubleLinkNode<E> p = this.head;// p指向头结点
            int i = 0;
            while (p != null && i < index) {// 遍历双链表
                i++;
                p = p.next;
            }
            if (p != null) {
                DoubleLinkNode<E> q = new DoubleLinkNode<E>(element);// 新建q结点
                q.prev = p.prev;
                q.next = p;
                p.prev.next = q;
                p.prev = q;
                this.n++;// 链表长度加1
            }
        }
        return true;
    }

    /**
     * 在双链表的最后插入元素对象
     */
    @Override
    public boolean add(E element) {
        if (element == null) {// 不允许插入空元素
            return false;
        }
        DoubleLinkNode<E> p = this.head;
        while (p.next != null) {// 遍历双链表
            p = p.next;
        }
        DoubleLinkNode<E> q = new DoubleLinkNode<E>(element);// 创建要插入的结点q
        p.next = q;
        q.prev = p;
        this.n++;// 链表长度加1
        return true;
    }

代码解释:

p指向双链表的某一个结点,在p结点之前插入q结点的示意图如下所示:

p结点之前插入q结点的语句如下所示:
DoubleLinkNode q = new DoubleLinkNode(element);
q.prev = p.prev;
q.next = p;
p.prev.next = q;
p.prev = q;

4. 双链表的删除

在双链表中删除节点只需要改变某些链接,不需要移动节点数据元素,代码如下所示:

/**
     * 移除索引index处的结点,操作成功返回被移除的对象,失败则返回null
     */
    @Override
    public E remove(int index) {
        E old = null;
        if (index >= 0) {// 要删除元素的索引不能小于0
            if (index == 0) {// 等于0是头结点,不能移除头指针,如果值是0,赋值为1
                index = 1;
            }
            DoubleLinkNode<E> p = this.head;// p结点指向头结点
            int i = 0;
            while (p != null && i < index) {// 遍历寻找元素
                i++;
                p = p.next;
            }
            if (p != null) {
                old = p.data;
                p.prev.next = p.next;
                if (p.next != null) {
                    p.next.prev = p.prev;
                }
                this.n--;// 双链表长度减1
            }
        }
        return old;
    }

代码解释:

p指向双链表中的某个结点,删除p指向的结点示意图如下所示:

删除p指向的结点的执行语句如下所示:
p.prev.next = p.next;
if (p.next != null) {
p.next.prev = p.prev;
}

5. 清空双链表

代码如下所示:


/** * 清空双链表 */ @Override public void clear() { this.head.next = null; this.n = 0; }

代码解释:

this.head.next = null时,双链表为空。

6. 重写toString()方法

代码如下所示:

@Override
    public String toString() {// 返回所有元素值对应的字符串
        String str = "(";
        DoubleLinkNode<E> p = this.head.next;
        while (p != null) {
            str += p.data.toString();
            p = p.next;
            if (p != null) {
                str += ", ";
            }
        }
        return str + ")";
    }

三.测试

测试代码如下所示:

package org.light4j.dataStructure.linearList.linkList.doubleLink;

import org.light4j.dataStructure.linearList.LList;

public class Test {
    public static void main(String[] args) {
        LList<String> list = new DoubleLinkedList<String>();
        list.add("A");
        list.add("B");
        System.out.println(list.toString());
        list.remove(2);// 移除元素
        System.out.println(list.toString());
        list.add(5, "C");// 追加元素
        list.add(2, "D");//追加元素
        System.out.println(list.toString());
    }
}

运行效果如下图所示:

四.源代码示例

github地址:点击查看
码云地址:点击查看

打赏
欢迎关注人生设计师的微信公众账号
公众号ID:longjiazuoA

未经允许不得转载:人生设计师 » 自己实现集合框架(八):双链表的实现

分享到:更多 ()

人生设计师-接受不同的声音

联系我关于我