• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

数据结构笔记总结(3.3)使用链表的虚拟头结点

极客笔记 Geekerstar 12个月前 (05-11) 389次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

使用链表的虚拟头结点

上一节我们学习了如何为链表添加元素,但是在添加元素的过程中我们遇到了一个问题。

就是在向链表任意一个地方添加元素的时候,在链表头添加元素和在链表的其他位置添加元素逻辑上会有差别。

究其原因,是因为我们对链表添加元素的过程要找到那个待添加位置之前的一个节点,但是由于对链表头来说,它没有前一个节点,所以在逻辑上会特殊一些。

不过在链表的实现中,有一个非常有用的技巧,把对链表头的特殊操作与其他操作统一起来,也就是可以自己创造一个链表头前面的节点。

这个之前的节点其实不存储任一个元素,所以这个元素写成null,将这个空节点称之为dummyHead,也就是虚拟头结点。

这样对于链表来说,它的第一个元素就是dummyHead的next所对应的节点的元素而不是dummyHead对应节点的元素。

dummyHead节点的元素是不存在的,对用户来说也是没有意义的,只是为了我们编写逻辑方便而出现的一个虚拟的头结点。

所以这点对用户来说是可以屏蔽的,用户不知道我们链表里有没有虚拟头结点,这点比较类似于以前实现的循环队列。

代码实现

修改之前的代码,具体代码如下:

public class LinkedList {

    private class Node{
        public E e;
        public Node next;

        public Node(E e, Node next){
            this.e = e;
            this.next = next;
        }

        public Node(E e){
            this(e, null);
        }

        public Node(){
            this(null, null);
        }

        @Override
        public String toString(){
            return e.toString();
        }
    }

    private Node dummyHead;
    private int size;

    public LinkedList(){
        dummyHead = new Node();
        size = 0;
    }

    // 获取链表中的元素个数
    public int getSize(){
        return size;
    }

    // 返回链表是否为空
    public boolean isEmpty(){
        return size == 0;
    }

    // 在链表的index(0-based)位置添加新的元素e
    // 在链表中不是一个常用的操作,练习用:)
    public void add(int index, E e){

        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Illegal index.");

        Node prev = dummyHead;
        for(int i = 0 ; i < index ; i ++)
            prev = prev.next;

        prev.next = new Node(e, prev.next);
        size ++;
    }

    // 在链表头添加新的元素e
    public void addFirst(E e){
        add(0, e);
    }

    // 在链表末尾添加新的元素e
    public void addLast(E e){
        add(size, e);
    }
}

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(3.3)使用链表的虚拟头结点
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00