Java知网

  • 首页
  • Spring Boot
  • 面试精选
  • 程序人生
  • 资源
  • 友链
  • 关于我
  1. 首页
  2. Java
  3. 正文

揭开链表的真面目

2021年3月17日 228点热度 1人点赞 1条评论

链表是一种常见的数据结构,链表是由一连串的结点组成,这个节点就是链结点,每个链结点都由数据域和指针域两部分组成。

使用链表结构可以克服数组结构需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。

链表比较好的一种理解是:将链表看成一个火车,每个车厢之间都是相互连接的,只要找到火车头,就可以找到具体的车身。链表也是,我们只关心它的头。

一、单向链表

1.1 单向链表原理图

单向链表的一个链结点包含数据域和下一个链结点的指针。头结点也包含数据域和指针域,但是一般为了方便查找,头节点不写数据,最后一个结点的指针指向空。

image-20200808183059381

1.2 实现单向链表的存储等操作

创建一个链结点的实体类

public class Node {

    // 数据域
    public long data;
    // 指针域
    public Node next;

    public Node(long value){
        this.data = value;
    }
}

1.2.1 插入一个节点

在头节点后插入一个结点,第一步需要将新插入的结点指向头结点指向的结点,第二部将头结点指向新插入的结点。插入结点只需要改变一个引用,所以复杂度为O(1)。

image-20200808190449283

public class LinkList {

    private Node head;
    /**
     * 在头节点之后插入一个节点
     */
    public void insertFirst(long value){
        Node node = new Node(value);
        node.next = head;
        head = node;
    }
}

1.2.2 头结点后删除一个结点

在头结点后删除一个结点,就是让头结点指向这个结点的下一个结点。复杂度也是O(1)。

image-20200808191246716

public Node deleteFirst(){
    Node tmp = head;
    head = tmp.next;
    return tmp;
}

1.2.3 根据数据域查找结点

查找需要比对每个结点的数据,理论上查找一个结点平均需要N/2次,所以复杂度为O(N)。

public Node find(long value){

    Node current = head;
    while (current.data != value){
        if(current.next == null){
            return null;
        }
        current = current.next;
    }
    return current;
}

1.2.4 根据数据与删除结点

查找需要比对每个结点的数据,理论上删除一个结点平均需要N/2次,所以复杂度为O(N)。

public Node delete(int value){
    Node current = head;
    // 当前结点的前一个结点
    Node pre = head;
    while (current.data != value){
        if(current.next == null){
            return null;
        }
        pre = current;
        current = current.next;
    }
    if(current == head){
        head = head.next;
    }else{
        pre.next = current.next;
    }
    return current;
}

二、双端链表

2.1 双端链表原理图

双端链表是在单向链表的基础上,头结点增加了一个尾结点的引用。

image-20200808193151491

2.2 实现双端链表的存储等操作

2.2.1 从头部插入结点

如果链表为空,则设置尾结点就是新添加的结点。复杂度为O(1)。

public class FirstLastLinkList {

    private Node first;
    private Node last;
    /**
     * 在头结点之后插入一个节点
     */
    public void insertFirst(long value){
        Node node = new Node(value);
        if(first == null){
            last = node;
        }
        node.next = first;
        first = node;
    }
}

2.2.2 从尾部插入结点

如果链表为空,则设置头结点为新添加的结点,否则设置尾结点的后一个结点为新添加的结点。复杂度为O(1)。

public void insertLast(long value){
    Node node = new Node(value);
    if(first == null){
        first = node;
    }else{
        last.next = node;
    }
    last = node;
}

2.2.3 从头部进行删除

判断头结点是否有下一个结点,如果没有则设置尾结点为null,复杂度为O(1)。

public Node deleteFirst(){

    Node tmp = first;
    if(first.next == null){
        last = null;
    }
    first = tmp.next;
    return tmp;
}

三、双向链表

3.1 双向链表原理图

每个结点除了保存对后一个结点的引用外,还保存着对前一个结点的引用。

image-20200809101236423

3.2 实现双向链表的存储等操作

链结点实体类

public class Node {

    // 数据域
    public long data;
    // 后一个结点指针域
    public Node1 next;
    // 前一个结点指针域
    public Node prev;

    public Node(long value){
        this.data = value;
    }
}

3.2.1 从头部插入结点

如果链表为空,则设置尾结点为新添加的结点,如果不为空,还需要设置头结点的前一个结点为新添加的结点。插入结点只需要改变两个结点的引用,所以复杂度为O(1)。

image-20200809100404652

public class DoubleLinkList {

    private Node first;
    private Node last;

    /**
     * 在头结点之后插入一个节点
     */
    public void insertFirst(long value){
        Node node = new Node(value);
        if(first == null){
            last = node;
        } else{
            first.prev = node;
        }
        node.next = first;
        first = node;
    }
}

3.2.2 从尾部插入结点

如果链表为空,则设置头结点为新添加的结点,否则设置尾结点的后一个结点为新添加的结点。同时设置新添加的结点的前一个结点为尾结点。插入结点只需要改变1个结点的引用,所以复杂度为O(1)。

public void insertLast(long value){
    Node node = new Node(value);
    if(first == null){
        first = node;
    }else{
        last.next = node;
        node.prev = last;
    }
    last = node;
}

3.2.3 从头部删除结点

判断头结点是否有下一个结点,如果没有则设置尾结点为null,否则设置头结点的下一个结点的prev为null。复杂度也为O(1)。

image-20200809101842520

public Node deleteFirst(){

    Node tmp = first;
    if(first.next == null){
        last = null;
    }else{
        first.next.prev = null;
    }
    first = tmp.next;
    return tmp;
}

3.2.4 从尾部删除结点

如果头结点后没有其他结点,则设置头结点为null,否则设置尾结点的前一个结点的next为null,设置尾结点为前一个结点。复杂度为O(1)。

public Node deleteLast(){

    Node tmp = last; 
    if(first.next == null){
        first = null;
    }else{
        last.prev.next = null;  
    }
    last = last.prev;
    return last;
}

四、总结

链表包含一个头结点和多个结点,头结点包含一个引用,这个引用通常叫做first,它指向链表的第一个链结点。结点的next为null,则意味着这个结点时尾结点。与数组相比,链表更适合做插入、删除操作,而查找操作的复杂度更高。还有一个优势就是链表不需要初始化内存大小,不会造成内存溢出(数组中插入元素个数超过数组长度)或内存浪费(声明的数组长度比实际放的元素长)。

本文由 Java知网 创作
禁止未经授权转载,违者依法追究相关法律责任

相关文章:

  1. 从面试角度分析LinkedList源码
  2. 面试官:说一下LRU原理和redis实现
标签: 数据结构
最后更新:2021年9月4日

javatip

这个人很懒,什么都没留下

点赞
< 上一篇
下一篇 >

文章评论

  • javatip

    写的不错,赞一个

    2021年3月18日
    回复
  • 取消回复
    搜一搜
    扫一扫
      关注公众号
    • 技术干货推送
    • 免费资料领取
    • 定时福利发放
    分类
    • Java / 110篇
    • Mysql / 17篇
    • Redis / 10篇
    • Spring Boot / 29篇
    • Spring Cloud / 16篇
    • 消息队列 / 14篇
    • 程序人生 / 21篇
    • 资源 / 3篇
    • 面试 / 23篇
    归档
    • 2022年4月 / 1篇
    • 2022年1月 / 1篇
    • 2021年12月 / 9篇
    • 2021年11月 / 2篇
    • 2021年9月 / 10篇
    • 2021年8月 / 4篇
    • 2021年7月 / 2篇
    • 2021年6月 / 10篇
    • 2021年5月 / 18篇
    • 2021年4月 / 75篇
    • 2021年3月 / 78篇

    COPYRIGHT © 2021 javatip.cn. ALL RIGHTS RESERVED.

    陇ICP备19004310号-2

    甘公网安备 62010202003150号