淘先锋技术网

首页 1 2 3 4 5 6 7

ArrayList的缺陷

【数据结构】 ArrayList简介与实战中我们已经熟悉了ArrayList的使用,并且进行了简单模拟实现。通过源码知道,ArrayList底层使用数组来存储元素

由于其底层是一段连续空间,当在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低,因此ArrayList不适合做任意位置插入和删除比较多的场景。 因此:java集合中又引入了LinkedList,即链表结构

链表

链表的概念及结构

链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现

就如同火车中间通过链条链接的一个道理
在这里插入图片描述

链表的大概结构如下所示:

在这里插入图片描述

链表的每一节都含有相应的数据与下一节的地址,一般我们会记录起始节点,可以用来我们访问该链表,最后一个节点不含有下一节点的地址,置为null;

链表的分类

实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:

单向或者双向

在这里插入图片描述

带头或者不带头

在这里插入图片描述

循环或者非循环

在这里插入图片描述
虽然有这么多的链表的结构,但是我们重点掌握两种:

  • 无头单向非循环链表结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多
    在这里插入图片描述
  • 无头双向链表:在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

单链表的实现

接下来我们来实现一个无头单向非循环链表实现,并实现一些相应的功能

创建单链表

博主在这里创建一个类为MyLinkedList类,我们将在这里面实现我们的无头单向非循环链表

创建单链表其实很简单,我们需要建立一个类,类里面放你需要放的数据元素,以及该类类型的元素,用于储存下一节点的地址

然后我们还需要一个变量来记录其实节点,在这里我们用一个内部类在MyLinkedList类进行表示,并在createLink方法里进行各个节点的创建并赋值,然后将这些节点链接起来

在这里插入图片描述

代码实现如下

public class MyLinkedList {
    class Node {
        public int val;
        public Node next;

        public Node(int val) {
            this.val = val;
        }
    }
    public Node head;// 代表当前链表的头节点的引用
    public void createLink() {
        Node node1 = new Node(11);
        Node node2 = new Node(22);
        Node node3 = new Node(33);
        Node node4 = new Node(44);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4; /* */
        head = node1;
    }
}

遍历链表

写好的链表,我们来进行打印一下看看是否创建成功

我们的head为我们的头节点,也就是我们遍历的起点,但是由于该单链表是单向的,如果使用头节点进行遍历的话,会导致后面找不到头节点,所以我们这里重新创建一个变量进行遍历。

由于每一节点里的next里面都存储着我们下一节点的地址,所以当我们访问完当前节点的元素后,将当前节点的next赋给我们所创建的遍历变量即可;

由于最后一个节点里next里面为null,所以我们将它作为结束条件

代码实现如下

public void disPlay() {
        Node sur = head;
        while(sur  != null) {
            System.out.print(sur.val+" ");
            sur = sur.next;
        }
    }

得到单链表的长度

进行遍历,并用一个数进行记录,最后进行返回就行

代码实现如下

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

查找是否包含关键字

我们只需要对该链表进行遍历,然后一一比对就好,大致实现过程与遍历链表相同

代码实现如下

 //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        Node cur = head;
        while (cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

头插法

将第一个节点赋给我们新添加的节点里面的next

并且将新添加的节点赋给head,作为新的头节点
在这里插入图片描述

代码实现如下

  public void addFirst(int data){
        Node node = new Node(data);
        node.next = head;
        head = node;
    }

注意:一定要注意赋值的顺序

尾插法

我们首先对该链表进行遍历,当遍历到最后一个节点时

将最后一个节点里的next赋为我们新增的节点即可。

如果该链表为空,直接将该新增节点设为头节点就好
在这里插入图片描述

代码实现如下

 public void addLast(int data){
        Node node = new Node(data);
        if(head == null) {
            head = node;
            return;
        }
        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }

任意位置插入

首先我们需要对需要插入的位置进行遍历,必须为合法,如果不合法,我们会抛出一个异常进行提醒,这里我们自定义了一个异常如下

public class ListIndexOutOfException extends RuntimeException{
    public ListIndexOutOfException() {
    }

    public ListIndexOutOfException(String message) {
        super(message);
    }
}

任意位置插入,我们可以分为种情况

  • 插在开头
  • 插在结尾
  • 插在中间

前两种我们已经实现了,我们现在只需要实现插在中间就好

我们对该单链表进行编号,第一个节点为我们的0下标。我们需要遍历单链表,找到所需要插入下标的前一个节点

将该节点的next设为我们新增的节点,将新增节点里面的next设为下一节点
在这里插入图片描述
代码实现如下

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data)
            throws ListIndexOutOfException{
        checkIndex(index);
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == size()) {
            addLast(data);
            return;
        }
        Node cur = findIndexSubOne(index);
        Node node = new Node(data);
        node.next = cur.next;
        cur.next = node;
    }

    /**
     * 找到 index-1位置的节点的地址
     * @param index
     * @return
     */
    private Node findIndexSubOne(int index) {
        Node cur = head;
        int count = 0;
        while (count != index-1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }
    private void checkIndex(int index) throws ListIndexOutOfException{
        if(index < 0 || index > size()) {
            throw new ListIndexOutOfException("index位置不合法");
        }
    }

删除第一次出现关键字为key的节点

分为四种情况

  • 一个节点都没有
  • 删除数据在第一个
  • 没有你要删除的数据
  • 有你要删除的数据且不是第一个

第一种情况判断是否为空后直接返回就好

第二种情况直接将头节点置为下一节点,也就时head=head.next;

第三种情况遍历单链表后,返回就好

第四种情况,找到所需要删除数据的前一节点,将所需要删除数据的前一节点的next设为当前需要删除数据节点的next
在这里插入图片描述

代码实现如下

//删除第一次出现关键字为key的节点 O(N)
    public void remove(int key){
        if(head == null) {
            return ;//一个节点都没有
        }
        if(head.val == key) {
            head = head.next;
            return;
        }
        Node cur = searchPrev(key);
        if(cur == null) {
            return;
        }
        Node del = cur.next;//要删除的节点
        cur.next = del.next;
    }

    /**
     * 找到关键字key的前一个节点
     * @param key
     * @return
     */
    private Node searchPrev(int key) {
        Node cur = head;
        while (cur.next != null) {
            if(cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;//没有你要删除的节点
    }

删除所有值为key的节点

我们依旧需要对该单链表进行判断,如果为空,就直接返回

由于我们需要删除很多个这样的节点,但是我们的单链表却是单向的,按照上面的写法,我们则需要遍历很多次单链表,大大的增加了复杂度,我们为了降低时间复杂度,使它降为O(N);

我们设两个遍历节点,进行遍历,一个在前为cur,一个在后prev
在这里插入图片描述

前面的cur负责进行遍历删除,后面的prev负责跟在cur后面记录cur的上一节点

当cur下一节点不是我们所要删除的元素时,这时候我们将prev变为我们当前节点的cur,而cur变为当前节点的next
在这里插入图片描述
当前的删除方法只能删除第一个节点以后的元素,所以我们还需要处理第一个元素是我们所需要删除的情况。

代码实现如下

//删除所有值为key的节点
    public void removeAllKey(int key){
        if(head == null) {
            return;
        }
        Node prev = head;
        Node cur = head.next;
        while (cur != null) {
            if(cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        if(head.val == key) {
            head = head.next;
        }
    }

回收链表

将头节点置为空就好。

代码实现如下

public void clear() {
        head = null;
    }

总结

关于《【数据结构】 链表简介与单链表的实现》就讲解到这儿,感谢大家的支持,欢迎各位留言交流以及批评指正,如果文章对您有帮助或者觉得作者写的还不错可以点一下关注,点赞,收藏支持一下!