链表和LinkedList

发布时间:2022-08-18 18:26

目录

1.链表

1.1 链表概念和结构

1.2 链表实现

1.3 力扣-牛客上的一些链表面试题

2.LinkedList

2.1 LinkedList的使用

2.1.1 LinkedList结构

2.1.2 LinkedList实现的List接口

2.1.3 LinkedList的使用 

2.1.4 LinkedList 的遍历 

2.2 LinkedList模拟实现

3. ArrayList和LinkedList的区别


1.链表

1.1 链表概念和结构

链表是一种在物理存储结构上非连续的存储结构,

数据元素的逻辑顺序是通过链表中引用链接的顺序实现的

链表和LinkedList_第1张图片

 注意:(1)链式存储结构在逻辑上是连续的,在物理上不一定连续

            (2)结点从堆中申请

说明,链表结构有8种

链表和LinkedList_第2张图片

常用有两种

(1)单向 不带头 非循环:这个的特点是结构简单,所以实际中用作其他数据结构的子结构

(2)双向 无头 :在java集合框架中LinkedList底层就是无头双向循环链表实现的 


1.2 链表实现

下面来写一个无头单向非循环链表的实现

先根据单链表结点写一个节点类

    static class Node{
        public int val;
        public Node next;
        public Node(int val) {
            this.val = val;
        }
    }
    public Node head;

(1)打印单链表display()

    public void display() {
        while(this.head != null) {
            System.out.print(this.head.val+" ");
            this.head = this.head.next;
        }
        System.out.println();
    }

(2)查找是否包含关键字key是否在单链表当中contains()

链表和LinkedList_第3张图片

    public boolean contains(int key) {
        Node cur =this.head;
        while(cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

(3)求链表长度size()

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

(4)头插法addFirst()

链表和LinkedList_第4张图片

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

 (5)尾插法addLast()

链表和LinkedList_第5张图片

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

(6)任意位置插入,第一个数据节点为0号下标addIndex()

链表和LinkedList_第6张图片

 先写一个checkIndex()来判断index合不合法

    private void checkIndex(int index) {
        if (index < 0 || index > size()) {
            throw new IndexNotLegalException("index位置不合法");
        }
    }

如果不合法写一个异常

public class IndexNotLegalException extends RuntimeException{
    public IndexNotLegalException() {

    }
    public IndexNotLegalException(String msg) {
        super(msg);
    }
}

然后让cur走到index前一个节点findIndexSubOfOne()

    private Node findIndexSubOfOne(int index) {
        Node cur = head;
        while(index-1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

下面写index()

 public void addIndex(int index, int data) {
        checkIndex(index);
        if (index == 0) {//头插法
            addFirst(data);
            return;
        }
        if (index == size()) {//尾插法
            addLast(data);
            return;
        }
        Node node = new Node(data);
        Node cur = findIndexSubOfOne(index);
        node.next = cur.next;
        cur.next = node;
    }

(7)删除第一次出现关键字key的结点remove()

链表和LinkedList_第7张图片

  先找到所要删除结点的前驱searchPrevOfKey()

    private Node searchPrevOfKey(int key) {
        Node cur = this.head;
        while(cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

下面写remove()

    public void remove(int key) {
        //如果删除头结点
        if (head.val == key) {
            head = head.next;
            return;
        }
        Node cur = searchPrevOfKey(key);
        if (cur == null) return;
        Node del = cur.next;
        cur.next = del.next;
    }

(8)删除所有值为key的结点removeAllKey()

链表和LinkedList_第8张图片

 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;
        }
    }

(9)清空链表clear()

    public void clear() {
        this.head = null;
    }

1.3 力扣-牛客上的一些链表面试题

这个是我写的一篇链表的题,感兴趣的可以看一下

http://t.csdn.cn/B2BG2


 

2.LinkedList

2.1 LinkedList的使用

2.1.1 LinkedList结构

LinkedList底层是双向链表的结构,不是单链表

双向链表的节点组成 

链表和LinkedList_第9张图片

 双向链表实现图示

链表和LinkedList_第10张图片

特点:

(1)last记录保存最后一个节点的地址,如果要进行尾插法时,直接last.next就可以了 

(2)双向链表的遍历是双向的


 

2.1.2 LinkedList实现的List接口

链表和LinkedList_第11张图片

 注意:

(1)LinkedList实现了List接口

(2)LinkedList的底层使用了双向链表

(3)LinkedList没有实现RandomAccess接口,所以LinkedList不支持随机访问

(4)LinkedList的任意位置插入和删除元素时效率比较高,时间复杂度为O(1)


2.1.3 LinkedList的使用 

LinkedList构造 (1)无参构造 (2)利用其他集合容器中元素构造List

    public static void main(String[] args) {
        List list = new LinkedList<>();
        
        List list1 = new ArrayList<>();
        list1.add("xawl");
        list1.add("xxgcxy");
        list1.add("rjgc");
        List list2 = new LinkedList<>(list1);
    }

2.1.4 LinkedList 的遍历 

(1)下标+for循环 (2)for-each(3)使用迭代器正向遍历(4)使用反向迭代器反向遍历

 public static void main(String[] args) {
        LinkedList list = new LinkedList<>();
        list.add(12);
        list.add(25);
        list.add(45);
        list.add(67);
        System.out.println("=====1.for+下标=======");
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
        System.out.println();
        System.out.println("======2.for-each======");
        for (int x : list) {
            System.out.print(x + " ");
        }
        System.out.println();
        System.out.println("=======3.迭代器-正向=====");
        ListIterator it = list.listIterator();
        while(it.hasNext()) {
            System.out.print(it.next() + " ");
        }
        System.out.println();
        System.out.println("=====4.反向迭代器-反向=====");
        ListIterator it2 = list.listIterator(list.size());
        while (it2.hasPrevious()) {
            System.out.print(it2.previous() + " ");
        }
    }

2.2 LinkedList模拟实现

先根据双向链表节点定义一个节点类

    static class ListNode {
        public int val;
        public ListNode prev;
        public ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
        public ListNode head;

(1)链表打印disPlay()

        public void display() {
            ListNode cur = head;
            while(cur != null) {
                System.out.print(cur.val + " ");
                cur = cur.next;
            }
            System.out.println();
        }

(2)查找包含关键字key是否在链表当中contains()

        public boolean contains(int key) {
            ListNode cur = head;
            while(cur != null) {
                if (cur.val == key){
                    return true;
                }
                cur = cur.next;
            }
            return true;
        }

(3)求链表长度size()

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

(4)头插法addFirst()

链表和LinkedList_第12张图片

        public void addFirst(int data) {
            ListNode node = new ListNode(data);
            if (head == null) {
                head = node;
                last = node;
            } else {
                node.next = head;
                head.prev = node;
                head = node;
            }
        }

(5)尾插法addLast() 

链表和LinkedList_第13张图片

        public void addLast(int data) {
            ListNode node = new ListNode(data);
            if (head == null) {
                head = node;
                last = node;
            } else {
                node.prev = last;
                last.next = node;
                last = last.next;
            }
        }

 (6)任意位置插入,第一个数据节点为0号下标addIndex()

先获得index下标节点findInde()

        private ListNode findIndex(int index) {
            ListNode cur = head;
            while(index != 0) {
                cur = cur.next;
                index--;
            }
            return cur;
        }

链表和LinkedList_第14张图片

        public void addIndex(int index, int data) {
            //1.检查index合法性
            if (index < 0 || index > size()) {
                throw new IndexNotlegalException("双向链表index不合法");
            }
            if (index == 0) {
                addFirst(data);
                return;
            }
            if (index ==size()) {
                addLast(data);
                return;
            }
            ListNode node = new ListNode(data);
            //2.获取当前的index位置的结点地址
            ListNode cur = findIndex(index);
            node.next = cur;
            cur.prev.next = node;
            node.prev = cur.prev;
            cur.prev = node;
        }

(7)删除第一次出现关键字为key的结点remove()

      public void remove(int key) {
            ListNode cur = head;
            while (cur != null) {
                //找到了删除
                if (cur.val == key) {
                    if (cur == head) {
                        //1.删除头部
                        head = head.next;
                        if (head != null) {
                            //防止只有一个节点
                            head.prev = null;
                        }
                    } else {
                        cur.prev.next = cur.next;
                        if (cur.next != null) {
                            //2.删除中间结点
                            cur.next.prev = cur.prev;
                        } else {
                            //3,删除尾部
                            last = cur.prev;
                        }
                    }
                    return;
                }
                cur = cur.next;
            }
        }

(8)删除所有值为key的结点removeAllkey()

前(7)中删除一个值为key的结点,然后就return返回了

这里删除所有的key,那就不要return了直接全部找出来删除

   public void removeAllKey(int key) {
            ListNode cur = head;
            while (cur != null) {
                //找到了删除
                if (cur.val == key) {
                    if (cur == head) {
                        //1.删除头部
                        head = head.next;
                        if (head != null) {
                            //防止只有一个节点
                            head.prev = null;
                        }
                    } else {
                        cur.prev.next = cur.next;
                        if (cur.next != null) {
                            //2.删除中间结点
                            cur.next.prev = cur.prev;
                        } else {
                            //3,删除尾部
                            last = cur.prev;
                        }
                    }
                }
                cur = cur.next;
            }
        }

(9)清除所有结点clear()

        public void clear() {
            head = null;
            last = null;
        }

3. ArrayList和LinkedList的区别

最直观的我们从二者的 增删查改 的时间复杂度进行比较

链表和LinkedList_第15张图片

下来简单说一下

相同点:

(1)ArrayList和LinkedList都实现了这三个接口 java.util.List(支持泛型,都能用来存放各种类数据类型的对象)、Cloneable(能支持克隆)、java.io.Serializable(能够支持序列化)

(2)ArrayList和LinkedList都不是线程安全的,如果要在多线程情况下调用它们,可以使用Collertions类中的静态方法SynchronizedList(),或者用Vector

不同点

ArrayList LinkedLIst
实现方式 动态数组 双向链表
存储空间 一定连续 逻辑上连续,物理上不一定
随机访问 支持高效的随机访问 不支持
应用场景 高效存储+频繁访问 任意位置频繁插入删除
内存占用 存储数据+结点指向后 消耗小 存储数据+结点指向前+指向后 消耗大
插入 空间不够时需要扩容 没有容量的概念,只需拉链条
非线程安全 基于动态数组实现的非线程安全的集合 基于链表实现的非线程安全的集合


 

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号