阅读 24

Java版-数据结构-链表

概要

之前我们分别学习了解了动态数组、栈、队列,其实他们的底层都是依托静态数组来实现的、只是通过我们定义的resize方法来动态扩容解决固定容量的问题,那么我们即将学习的链表,它其实是一种真正的动态数据结构。

介绍

链表是一种最简单的动态数据结构,它能够辅助组成其它的数据结构,链表中的元素可存储在内存中的任何地方(不需要连续的内存,这一点和我们的数组具有很大的区别,数组需要连续的内存),链表中的每个元素都存储了下一个元素的地址,从而使一系列随机的内存地址串接在一起

存储链表的数据的我们一般称为节点(Node),节点一般分为两部分,一部分存储我们真正的数据,而另外一部分存储的是下一个节点的引用地址。

class Node{
    private E e; // 存储的真正元素
    private Node next;  // 存储下一个node的引用地址(指向下一个node)
}
复制代码

比如现在我们将元素A、B、C三个节点添加到链表中,示意图如下:

image-20190327213801994

从图中节点A到节点B之间的箭头代表,节点A指向了节点BNodeA.next = NodeB),因为在实际业务中我们的链表长度不可能是无穷无尽的,基本上都是有限个节点,通常定义链表中的最后一个元素它的next存储的是NULL(空),换句话说,如果在链表中,一个节点的next是空(NULL)的话,那么它一定是最后一个节点(对应我们图中的C节点)。

根据我们上面介绍的链表基本结构,下面我们用代码定义一下链表的基本骨架(这里我们引入了一个虚拟的头结点,下面我们会作说明)

public class LinkedList<E> {
    /**
     * 虚拟的头结点
     */
    private Node dummyHead;
    /**
     * 链表中节点的个数
     */
    private int size;

    public LinkedList() {
        // 创建一个虚拟的头结点
        dummyHead = new Node();
    }


    // 节点定义
    private class Node {
        // 存储节点的元素
        public E e;
        // 存储下一个节点的地址
        public Node next;

        public Node() {

        }

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

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

        @Override
        public String toString() {
            return "Node{" +
                    "e=" + e +
                    ", next=" + next +
                    '}';
        }
    }
}
复制代码

后面我们对链表的添加节点、删除节点以及查询节点,代码实现都会基于这个基本骨架

向链表中添加节点

思路分析:

一般我们向链表中添加节点,基本思路:找到添加节点位置的前一个节点preNode,然后再改变链表的地址引用;由于链表的第一个节点也就是头结点没有前节点,此时我们为了操作方便,为链表新增了不存储任何元素的一个虚拟的头结点dummyHead(不是必须的,对用户来讲是不可见的),其实链表中真正的第一个节点是节点AdummyHead.next),这样我们就能保证了,链表中存储元素的节点都有前一个节点。

image-20190328144225867

下面我们来看一下,如果现在有一个节点D,我们准备把它插入到节点B的位置,我们需要做哪些操作

第一步:我们首先要找到节点B的前一个节点,也就是节点A

第二步:将新节点D的指向指到节点BNodeD.next = NodeA.next),然后再将节点A的指向,指到节点DNodeA.next = NodeD),这样我们的节点就能串接起来了

image-20190330090951086

代码实现:
/**
  * 向链表中指定位置插入节点(学习使用,真正插入不会指定索引)
  *
  * @param index 索引的位置
  * @param e 节点元素
  */
public void add(int index, E e) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("不是有效的索引");
    }

    Node prev = dummyHead;

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

    // 新建一个节点,进行挂接
    Node node = new Node(e);
    node.next = prev.next;
    prev.next = node;

    size++;
}
复制代码

链表的遍历

进行链表遍历,我们需要从链表中真正的第一个元素开始,也就是dummyHead.next

/**
  * 获取链表中index位置的元素
  *
  * @param index  索引的位置
  * @return  节点的元素
  */
public E get(int index) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("不是有效的索引");
    }
    Node cur = dummyHead.next;
    for (int i = 0; i < index; i++) {
        cur = cur.next;
    }
    return cur.e;
}
复制代码

修改链表中元素

/**
  * 修改链表中index位置节点的元素
  *
  * @param index 索引的位置
  * @param e 节点的元素
  */
public void set(int index, E e) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("不是有效的索引");
    }
    Node cur = dummyHead.next;
    for (int i = 0; i < index; i++) {
        cur = cur.next;
    }
    cur.e = e;
}
复制代码

查找链表中是否包含某元素

/**
  * 查找链表中是否包含元素e
  *
  * @param e
  * @return
  */
public boolean contains(E e) {
    Node cur = dummyHead.next;
    while (cur != null) {
        if (cur.e.equals(e)) {
            return true;
        }
        cur = cur.next;
    }
    return false;
}
复制代码

删除链表中的元素

image-20190330093907204

在链表中删除元素,与在链表中添加元素有点类似

第一步:我们首先找到删除节点位置的前一个节点,我们用prev表示,被删除的节点我们用delNode表示

第二步:改变链表的引用地址:prev.next = delNode.next(等同于,将节点在链表中删除)

/**
  * 删除链表中index位置的节点
  *
  * @param index
  */
public void remove(int index) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("不是有效的索引");
    }

    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--;
}
复制代码

完整版代码GitHub仓库地址:Java版数据结构-链表 欢迎大家【关注】和【Star

至此笔者已经为大家带来了数据结构:静态数组、动态数组、栈、数组队列、循环队列、链表;接下来,笔者还会一一的实现其它常见的数组结构,大家一起加油!

  • 静态数组
  • 动态数组
  • 数组队列
  • 循环队列
  • 链表
  • 循环链表
  • 二分搜索树
  • 优先队列
  • 线段树
  • 字典树
  • AVL
  • 红黑树
  • 哈希表
  • ....

持续更新中,欢迎大家关注公众号:小白程序之路(whiteontheroad),第一时间获取最新信息!!!

小白程序之路

笔者博客地址:http:www.gulj.cn
关注下面的标签,发现更多相似文章
评论