投稿
  1. 极客之音首页
  2. 技术随笔

数据结构之链表（LinkedList详解）

小半 • • 技术随笔 • 阅读 212

导读：本篇文章讲解 数据结构之链表（LinkedList详解），希望对大家有帮助，欢迎收藏，转发！站点地址：www.bmabk.com

 

文章目录

  • 一、什么是LinkedList？
  • 二、LinkedList的使用
  • 三、LinkedList自实现
  • 四、链表实现逆序打印的两种方式（递归和非递归）
  • 五、ArrayList和LinkedList有什么区别？

一、什么是LinkedList？

LinkedList的底层是
双向链表结构(链表后面介绍)，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
 
在集合框架中，LinkedList也实现了List接口，具体如下：
d7695e27e19e41c0af85476fdb249112.png
1. LinkedList实现了
List接口
2. LinkedList的底层使用了
双向链表
3. LinkedList没有实现RandomAccess接口，因此LinkedList
不支持随机访问
4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
 

二、LinkedList的使用

构造方法：

方法 解释
LinkedList()
无参构造
public LinkedList(Collection<? extends E> c)
使用其他集合容器中元素构造List 
public static void main(String[] args) { 
  // 构造一个空的LinkedList 
  List<Integer> list1 = new LinkedList<>();
 
  List<String> list2 = new java.util.ArrayList<>(); 
  list2.add("JavaSE");
  list2.add("JavaWeb"); 
  list2.add("JavaEE"); 
  // 使用ArrayList构造LinkedList 
  List<String> list3 = new LinkedList<>(list2); 
}

 LinkedList的常用方法：

方法 解释
boolean add(E e)
尾插 e
void add(int index, E element)
将 e 插入到 index 位置
boolean addAll(Collection<? extends E> c)
尾插 c 中的元素
E remove(int index)
删除 index 位置元素
boolean remove(Object o)
删除遇到的第一个 o
E get(int index)
获取下标 index 位置元素
E set(int index, E element)
将下标 index 位置元素设置为 element
void clear()
清空
boolean contains(Object o)
判断 o 是否在线性表中
int indexOf(Object o)
返回第一个 o 所在下标
int lastIndexOf(Object o)
返回最后一个 o 的下标
List<E> subList(int fromIndex, int toIndex)
截取部分 list

LinkedList的遍历：(foreach遍历、使用迭代器遍历—正向遍历、使用反向迭代器—反向遍历

LinkedList<String> list = new LinkedList<>();
        list.add("javaSE");
        list.add("javaWeb");
        list.add("javaEE");
        // foreach遍历
        for (String x: list) {
            System.out.print(x + " ");
        }
        // 使用迭代器遍历---正向遍历
        ListIterator<String> list1 = list.listIterator();
        while (list1.hasNext()){
            System.out.print(list1.next()+" ");
        }
        // 使用反向迭代器---反向遍历
        ListIterator<String> lis2 = list.listIterator(list.size());
        while (lis2.hasPrevious()){
            System.out.print(lis2.previous()+" ");
        }

三、LinkedList自实现

public class MyLinkedList {
    static class ListNode{
        int val;
        ListNode pre;
        ListNode next;
        public ListNode(int val){
            this.val = val;
        }
    }
    public ListNode head;//头部
    public ListNode tail;//尾部

    public void addFirst(int data){
        ListNode node = new ListNode(data);
        if (head == null){
            head = node;
            tail = node;
            return;
        }
        node.next = head;
        head.pre = node;
        head = node;
    }
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if (head == null){
            head = node;
            tail = node;
            return;
        }
        tail.next = node;
        node.pre = tail;
        tail = node;
    }
    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data){
        if (index < 0 || index > size()){
            System.out.println("index位置不合法！");
            return false;
        }
        if (index == 0){
            addFirst(data);
            return true;
        }
        if (index == size()){
            addLast(data);
            return true;
        }
        ListNode indexNode = findNode(index);
        ListNode node = new ListNode(data);
        node.pre = indexNode.pre;
        indexNode.pre.next = node;
        node.next = indexNode;
        indexNode.pre = node;
        return true;
    }
    public ListNode findNode(int index){
        ListNode cur = head;
        while (index != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }
    public boolean contains(int key){
        ListNode cur = head;
        while (cur != null){
            if (cur.val == key)return true;
            cur = cur.next;
        }
        return false;
    }
    public void remove(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                if (cur == head) {
                    head = head.next;
                    if (head != null) {
                        head.pre = null;
                    } else {
                        tail = null;
                    }
                } else {
                    cur.pre.next = cur.next;
                    if (cur.next != null) {
                        cur.next.pre = cur.pre;
                    } else {
                        tail = tail.pre;
                    }
                }
                return;
            }
            cur = cur.next;
        }
    }

    public void removeAllKey(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                if (cur == head) {
                    head = head.next;
                    if (head != null) {
                        head.pre = null;
                    } else {
                        tail = null;
                    }
                } else {
                    cur.pre.next = cur.next;
                    if (cur.next != null) {
                        cur.next.pre = cur.pre;
                    } else {
                        tail = tail.pre;
                    }
                }
            }
            cur = cur.next;
        }
    }
    public int size(){
        ListNode cur = head;
        int count = 0;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }
    public void display(){
        ListNode cur = head;
        while (cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }
    public void clear(){
        ListNode cur = head;
        while (cur != null){
            ListNode temp = cur.next;
            cur.next = null;
            cur.pre = null;
            cur = temp;
        }
        head = null;
        tail = null;
    }
}

四、链表实现逆序打印的两种方式（递归和非递归）

递归逆序打印：

public void display(ListNode head) {
        if(head == null) {
            return;
        }
        if(head.next == null) {
            System.out.print(head.val+" ");
            return;
        }
        display(head.next);
        System.out.print(head.val+" ");
    }

非递归逆序打印（用栈实现）：

public void display(ListNode head) {
        if (head == null) {
            return;
        }
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        while (!stack.empty()) {
            ListNode ret = stack.pop();
            System.out.print(ret.val+" ");
        }
    }

 

五、ArrayList和LinkedList有什么区别？

 

ArrayList实质是顺序表，底层是一个数组。LinkedList实质是一个链表。

他们都具有增删查改的功能，但是在实现方式上有区别。比如在插入元素的时候，ArrayList往0位置上插入一个元素，就需把整个数组整体往后移动，时间复杂度为O(N)。而LinkedList只需要修改指向就可以了，时间复杂度为O(1)。但是ArrayList可以支持随机访问，时间复杂度为O(1)，所以一般情况下ArrayList顺序表适合频繁根据下标位置访问，LinkedList比较适合插入和删除比较频繁的情况。

从存储上来说，ArrayList顺序表在物理上和逻辑上都是连续的，但是在扩容的时候，可能会造成空间的浪费。而LinkedList在物理上不一定是连续的，在逻辑上是连续的，可以做到随用随取。

不同点 ArrayList LinkedList
存储空间上         
物理上逻辑上一定连续
逻辑上连续，但物理上不一定连续
随机访问
支持O(1)
不支持：O(N)
头插
需要搬移元素，效率低O(N)
只需修改引用的指向，时间复杂度为O(1)
插入
空间不够时需要扩容
没有容量的概念
应用场景
元素高效存储+频繁访问
任意位置插入和删除频繁

 

 

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/94465.html

赞 (0)
小半的头像小半
0 0

相关推荐

极客之音——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！