JAVA语言之最基础的动态数据结构:链表
王红 2019-04-10 来源 : 阅读 171 评论 0

摘要:本文主要向大家介绍了JAVA语言之最基础的动态数据结构:链表,通过具体的内容向大家展示,希望对大家学习JAVA语言有所帮助。

本文主要向大家介绍了JAVA语言之最基础的动态数据结构:链表,通过具体的内容向大家展示,希望对大家学习JAVA语言有所帮助。

JAVA语言之最基础的动态数据结构:链表

什么是链表

链表是一种线性结构,也是最基础的动态数据结构。我们在实现动态数组、栈以及队列时,底层都是依托的静态数组,靠resize来解决固定容量的问题,而链表是真正的动态数据结构。学习链表这种数据结构,能够更深入的理解引用(或者指针)以及递归。其中链表分为单链链表和双链链表,本文中所介绍的是单链链表。

链表中的数据是存储在一个个的节点中,如下这是一个最基本的节点结构:

class Node {
    E e;
    Node next;  // 节点中持有下一个节点的引用}

我们可以将链表想象成火车,每一节车厢就是一个节点,乘客乘坐在火车的车厢中,就相当于元素存储在链表的节点中。火车的每一节车厢都连接着下一节车厢,就像链表中的节点都会持有下一个节点的引用。火车的最后一节车厢没有连接任何车厢,就像链表中末尾的节点指向null一样:

JAVA语言之最基础的动态数据结构:链表

链表优缺点:

  • 优点:真正的动态结构,不需要处理固定容量的问题,从中间插入、删除节点很方便,相较于数组要灵活

  • 缺点:丧失了随机访问的能力,不能像数组那种直接通过索引访问

废话不多说,我们开始来编写链表这个数据结构吧,首先来实现链表中的节点结构以及链表的一些简单方法,代码如下:

/**
 * @program: Data-Structure
 * @description: 链表数据结构实现
 * @author: 01
 * @create: 2018-11-08 15:37
 **/public class LinkedList<E> {    /**
     * 链表中的节点结构
     */    private class Node {
        E e;
        Node next;        public Node() {            this(null, null);
        }        public Node(E e) {            this(e, null);
        }        public Node(E e, Node next) {            this.e = e;            this.next = next;
        }        @Override        public String toString() {            return e.toString();
        }
    }    /**
     * 头节点
     */    private Node head;    /**
     * 链表中元素的个数
     */    private int size;    public LinkedList() {        this.head = null;        this.size = 0;
    }    /**
     * 获取链表中的元素个数
     *
     * @return 元素个数
     */    public int getSize() {        return size;
    }    /**
     * 链表是否为空
     *
     * @return 为空返回true,否则返回false
     */    public boolean isEmpty() {        return size == 0;
    }    
}

在链表中添加元素

我们在为数组添加元素时,最方便的添加方式就是从数组后面进行添加,因为size总是指向数组最后一个元素+1的位置,所以利用size变量我们可以很轻易的完成元素的添加。

而在链表中则相反,我们在链表头添加新的元素最方便,因为链表内维护了一个head变量,即链表的头部,我们只需要将新的元素放入一个新的节点中,然后将新节点内的next变量指向head,最后把head指向这个新节点就完成了元素的添加:

JAVA语言之最基础的动态数据结构:链表

我们来实现这个在链表头添加新的元素的方法,代码如下:

/**
 * 在链表头添加新的元素e
 *
 * @param e 新的元素
 */public void addFirst(E e) {
    Node node = new Node(e);
    node.next = head;
    head = node;    // 以上三句代码完全可以直接使用以下一句代码完成,    // 但为了让逻辑更清晰所以这里特地将代码分解了    // head = new Node(e, head);

    size++;
}

然后我们来看看如何在链表中指定的位置插入新的节点,虽然这在链表中不是一个常用的操作,但是有些链表相关的题目会涉及到这种操作,所以我们还是得了解一下。例如我们现在要往“索引”为2的位置插入一个新的节点,该如何实现:

JAVA语言之最基础的动态数据结构:链表

虽然链表中没有真正的索引,但是为了实现在指定的位置插入新的节点,我们得引用索引这个概念。如上图中,把链表头看作是索引0,下一个节点看作索引1,以此类推。然后我们还需要有一个prev变量,通过循环移动这个变量去寻找指定的“索引” - 1 的位置,找到之后将新节点的next指向prev的next,prev的next再指向新的节点,即可完成这个插入节点的逻辑,所以关键点就是找到要添加的节点的前一个节点:

JAVA语言之最基础的动态数据结构:链表

具体的实现代码如下:

/**
 * 在链表的index(0-based)位置添加新的元素e
 *
 * @param index 元素添加的位置
 * @param e     新的元素
 */public void add(int index, E e) {    // 检查索引是否合法    if (index < 0 || index > size) {        throw new IllegalArgumentException(""Add failed. Illegal index."");
    }    // 链表头添加需特殊处理    if (index == 0) {
        addFirst(e);
    } else {
        Node prev = head;        // 移动prev到index - 1的位置        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }

        Node node = new Node(e);
        node.next = prev.next;
        prev.next = node;        // 同样,以上三句代码可以一句代码完成        // prev.next = new Node(e, prev.next);

        size++;
    }
}

基于以上这个方法,我们就可以轻易的实现在链表末尾添加新的元素:

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

使用链表的虚拟头节点

在上一小节中,我们实现向指定位置插入元素的代码里,需对链表头的位置特殊处理,因为链表头没有上一个节点。很多时候使用链表的都需要进行类似的特殊处理,并不是很优雅,所以本小节就是介绍如何优雅的解决这个问题。

之所以要进行特殊处理,主要原因还是head没有上一个节点,初始化prev的时候只能指向head,既然这样我们就给它前面加一个节点好了,这个节点不存储任何数据,仅作为一个虚拟节点。这也是编写链表结构时经常使用到的技巧,添加这么一个节点就可以统一链表的操作逻辑:

JAVA语言之最基础的动态数据结构:链表

修改后的代码如下:

public class LinkedList<E> {
    ...    /**
     * 虚拟头节点
     */    private Node dummyHead;    /**
     * 链表中元素的个数
     */    private int size;    public LinkedList() {        this.dummyHead = new Node(null, null);        this.size = 0;
    }    /**
     * 在链表的index(0-based)位置添加新的元素e
     *
     * @param index 元素添加的位置
     * @param e     新的元素
     */    public void add(int index, E e) {        if (index < 0 || index > size) {            throw new IllegalArgumentException(""Add failed. Illegal index."");
        }

        Node prev = dummyHead;        // 移动prev到index前一个节点的位置        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }

        Node node = new Node(e);
        node.next = prev.next;
        prev.next = node;        // 同样,以上三句代码可以一句代码完成        // prev.next = new Node(e, prev.next);

        size++;
    }    /**
     * 在链表头添加新的元素e
     *
     * @param e 新的元素
     */    public void addFirst(E e) {
        add(0, e);
    }    /**
     * 在链表末尾添加新的元素e
     *
     * @param e 新的元素
     */    public void addLast(E e) {
        add(size, e);
    }
}

链表的遍历、查询和修改

有了以上小节的基础,接下来我们实现链表的遍历、查询和修改就很简单了,代码如下:

/**
 * 获取链表的第index(0-based)个位置的元素
 *
 * @param index
 * @return
 */public E get(int index) {    if (index < 0 || index >= size) {        throw new IllegalArgumentException(""Get failed. Illegal index."");
    }

    Node cur = dummyHead.next;    for (int i = 0; i < index; i++) {
        cur = cur.next;
    }    return cur.e;
}/**
 * 获取链表中的第一个元素
 *
 * @return
 */public E getFirst() {    return get(0);
}/**
 * 获取链表中的最后一个元素
 *
 * @return
 */public E getLast() {    return get(size - 1);
}/**
 * 修改链表的第index(0-based)个位置的元素为e
 *
 * @param index
 * @param e
 */public void set(int index, E e) {    if (index < 0 || index >= size) {        throw new IllegalArgumentException(""Set failed. Illegal index."");
    }

    Node cur = dummyHead.next;    for (int i = 0; i < index; i++) {
        cur = cur.next;
    }

    cur.e = e;
}/**
 * 查找链表中是否包含元素e
 *
 * @param e
 * @return
 */public boolean contain(E e) {
    Node cur = dummyHead.next;    // 第一种遍历链表的方式    while (cur != null) {        if (cur.e.equals(e)) {            return true;
        }
        cur = cur.next;
    }    return false;
}@Overridepublic String toString() {    if (isEmpty()) {        return ""[]"";
    }

    StringBuilder sb = new StringBuilder();
    sb.append(String.format(""LinkedList: size = %d\n"", size));
    sb.append(""["");
    Node cur = dummyHead.next;    // 第二种遍历链表的方式    for (int i = 0; i < size; i++) {
        sb.append(cur.e).append("" -> "");
        cur = cur.next;
    }    // 第三种遍历链表的方式    // for (Node cur = dummyHead.next; cur != null; cur = cur.next) {    //     sb.append(cur.e).append("" -> "");    // }    return sb.append(""NULL]"").toString();
}

从链表中删除元素

最后我们要实现的链表操作就是从链表中删除元素,删除元素就相当于是删除链表中的节点。例如我要删除”索引“为2的节点,同样的我们也需要使用一个prev变量循环移动到要删除的节点的前一个节点上,此时把prev的next拿出来就是待删除的节点。删除节点也很简单,拿出待删除的节点后,将prev的next指向待删除节点的next:

JAVA语言之最基础的动态数据结构:链表

最后将待删除的节点指向一个null,让其脱离链表,这样就能够快速被垃圾回收,如此一来就完成了节点的删除:

JAVA语言之最基础的动态数据结构:链表

具体的实现代码如下:

/**
 * 从链表中删除第index(0-based)个位置的元素,并返回删除的元素
 *
 * @param index
 * @return 被删除的节点所存储的元素
 */public E remove(int index) {    if (index < 0 || index >= size) {        throw new IllegalArgumentException(""remove failed. Illegal index."");
    }

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

    Node delNode = prev.next;    // 把引用改变一下就完成了删除
    prev.next = delNode.next;
    delNode.next = null;
    size--;    return delNode.e;
}

基于以上这个方法,我们就可以很简单的实现如下两个方法:

/**
 * 删除链表中第一个元素
 *
 * @return 被删除的元素
 */public E removeFirst() {    return remove(0);
}/**
 * 删除链表中最后一个元素
 *
 * @return 被删除的元素
 */public E removeLast() {    return remove(size - 1);
}

最后我们来看一下我们实现的这个链表增删查改操作的时间复杂度:

addLast(e)         // O(n)addFirst(e)        // O(1)add(index, e)      // O(n)removeLast()       // O(n)removeFirst()      // O(1)remove(index)      // O(n)set(index, e)      // O(n)get(index)         // O(n)contain(e)         // O(n)

使用链表实现栈

从链表的addFirst和removeFirst方法的时间复杂度可以看到,如果只对链表头进行增、删操作的复杂度是O(1)的,只查询链表头的元素复杂度也是O(1)的。这时我们就可以想到使用链表来实现栈,用链表实现的栈其入栈出栈等操作时间复杂度也都是O(1)的,具体的实现代码如下:

/**
 * @program: Data-Structure
 * @description: 基于链表实现栈数据结构
 * @author: 01
 * @create: 2018-11-08 23:38
 **/public class LinkedListStack<E> implements Stack<E> {    private LinkedList<E> linkedList;    public LinkedListStack() {        this.linkedList = new LinkedList<>();
    }    @Override    public int getSize() {        return linkedList.getSize();
    }    @Override    public boolean isEmpty() {        return linkedList.isEmpty();
    }    @Override    public void push(E e) {
        linkedList.addFirst(e);
    }    @Override    public E pop() {        return linkedList.removeFirst();
    }    @Override    public E peek() {        return linkedList.getFirst();
    }    @Override    public String toString() {        if (isEmpty()) {            return ""[]"";
        }

        StringBuilder sb = new StringBuilder();
        sb.append(String.format(""LinkedListStack: size = %d\n"", getSize()));
        sb.append(""top ["");        for (int i = 0; i < getSize(); i++) {
            sb.append(linkedList.get(i));            if (i != getSize() - 1) {
                sb.append("", "");
            }
        }        return sb.append(""]"").toString();
    }    // 测试    public static void main(String[] args) {
        Stack<Integer> stack = new LinkedListStack<>();        for (int i = 0; i < 5; i++) {
            stack.push(i);
            System.out.println(stack);
        }

        stack.pop();
        System.out.println(stack);
    }
}

带有尾指针的链表:使用链表实现队列

上一小节我们基于链表很轻易的就实现了一个栈结构,本小节我们来看看如何使用链表实现队列结构,看看需要对链表进行哪些改进。

在编写代码之前,我们需要考虑到一个问题,在之前链表结构的实现代码中,只有一个head变量指向头节点,若我们直接使用这个链表实现队列的话,需要操作链尾的元素时,复杂度是O(n)的,因为需要遍历整个链表直到尾节点的位置。那么该如何避开遍历,在O(1)的复杂度下快速的找到尾节点呢?答案就是增加一个tail变量,让这个变量始终指向尾节点即可,这样我们操作尾节点的复杂度就是O(1)了。

除此之外,使用链表实现队列还有一个问题需要考虑,那就是从哪边入队元素,从哪边出队元素。我们之前编写的链表代码中,在链首添加元素是O(1)的,也是最简单方便的,所以我们要将链首作为入队的一端吗?答案是相反的,应该将链首作为出队的一端,链尾作为入队的一端。

因为我们实现的链表是单链结构,在这种情况下链首无论是作为入队还是出队的一端都是可以的,但是链尾不可以,链尾只能作为入队的一端。如果将链尾作为出队的一端,那么出队的复杂度将是O(n)的,需要遍历链表找到尾节点的上一个节点,然后将该节点的next指向null才能完成出队的操作。若是双链结构倒是无所谓,只需要通过tail变量就可以获取到上一个节点,不需要遍历链表去寻找。因此,我们需要将链首作为入队的一端,链尾作为出队的一端,这样无论是出队还是入队的时间复杂度都是O(1)。

具体的实现代码如下:

/**
 * @program: Data-Structure
 * @description: 基于链表实现的队列数据结构
 * @author: 01
 * @create: 2018-11-09 17:00
 **/public class LinkedListQueue<E> implements Queue<E> {    private class Node {
        E e;
        Node next;        public Node() {            this(null, null);
        }        public Node(E e) {            this(e, null);
        }        public Node(E e, Node next) {            this.e = e;            this.next = next;
        }        @Override        public String toString() {            return e.toString();
        }
    }    /**
     * 头节点
     */    private Node head;    /**
     * 尾节点
     */    private Node tail;    /**
     * 表示队列中的元素个数
     */    private int size;    @Override    public void enqueue(E e) {        if (tail == null) {            // 链表没有元素
            tail = new Node(e);
            head = tail;
        } else {            // 链尾入队元素
            tail.next = new Node(e);
            tail = tail.next;
        }
        size++;
    }    @Override    public E dequeue() {        if (isEmpty()) {            throw new IllegalArgumentException(""Can't dequeue from an empty queue."");
        }        // 链首出队元素
        Node retNode = head;
        head = head.next;
        retNode.next = null;        if (head == null) {            // 队列里没元素的话,尾节点需要置空
            tail = null;
        }
        size--;        return retNode.e;
    }    @Override    public E getFront() {        if (isEmpty()) {            throw new IllegalArgumentException(""Queue is empty."");
        }        return head.e;
    }    @Override    public int getSize() {        return size;
    }    @Override    public boolean isEmpty() {        return size == 0;
    }    @Override    public String toString() {        if (isEmpty()) {            return ""[]"";
        }

        StringBuilder sb = new StringBuilder();
        sb.append(String.format(""LinkedListQueue: size = %d\n"", getSize()));
        sb.append(""front ["");
        Node cur = head;        while (cur != null) {
            sb.append(cur.e).append("", "");
            cur = cur.next;
        }        return sb.append(""NULL] tail"").toString();
    }
}

本文由职坐标整理并发布,希望对同学们有所帮助。了解更多详情请关注编程语言JAVA频道!

本文由 @职坐标 发布于职坐标。未经许可,禁止转载。
喜欢 | 0 不喜欢 | 0
看完这篇文章有何感觉?已经有0人表态,0%的人喜欢 快给朋友分享吧~
评论(0)
后参与评论
本文作者 联系TA

2年研发与教学经验

  • 10
    文章
  • 706
    人气
  • 100%
    受欢迎度

已有1人表明态度,100%喜欢该老师!

进入TA的空间
名师指导 直通车
  • 索取资料 索取资料 索取资料
  • 答疑解惑 答疑解惑 答疑解惑
  • 技术交流 技术交流 技术交流
  • 职业测评 职业测评 职业测评
  • 面试技巧 面试技巧 面试技巧
  • 高薪秘笈 高薪秘笈 高薪秘笈
TA的其他文章 更多>>
JAVA语言之震惊,20年开发经验的技术总监不会搭建Java开发环境
职场感悟 100% 的用户喜欢
JAVA语言之Java 中不同的并行实现的性能比较
经验技巧 100% 的用户喜欢
JAVA语言之一次 HashSet 所引起的并发问题
经验技巧 0% 的用户喜欢
JAVA语言之Docker学习之搭建ActiveMQ消息服务
经验技巧 0% 的用户喜欢
JAVA语言之Java并发编程(9):死锁(含代码)
经验技巧 0% 的用户喜欢
其他海同名师 更多>>
刘新华
刘新华 联系TA
实力型。激情饱满,对专业充满热情
吴翠红
吴翠红 联系TA
独创“教、学、练、测”循环教学模式
吕益平
吕益平 联系TA
熟悉企业软件开发的产品设计及开发
黄泽民
黄泽民 联系TA
擅长javase核心技术
程钢
程钢 联系TA
擅长大型企业商业网站开发和管理
经验技巧30天热搜词 更多>>

您输入的评论内容中包含违禁敏感词

我知道了

助您圆梦职场 匹配合适岗位
验证码手机号,获得海同独家IT培训资料
选择就业方向:
人工智能物联网
大数据开发/分析
人工智能Python
Java全栈开发
WEB前端+H5

请输入正确的手机号码

请输入正确的验证码

获取验证码

您今天的短信下发次数太多了,明天再试试吧!

提交

我们会在第一时间安排职业规划师联系您!

您也可以联系我们的职业规划师咨询:

小职老师的微信号:13167058313
小职老师的微信号:13167058313

版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
 沪公网安备 31011502005948号    ICP许可  沪B2-20190160

站长统计