【数据结构二】链表和LinkedList详解

目录

链表和LinkedList

?1.链表的实现

2.LinkedList的使用

3.ArrayList和LinkedList的区别

4.链表OJ题训练

链表和LinkedList

? ? ? ? 当 在 ArrayList 任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后

搬移，时间复杂度为 O(n) ，效率比较低，因此 ArrayList 不适合做任意位置插入和删除比较多的场景。链表是一种 物理存储结构上非连续 存储结构，数据元素的 逻辑顺序 是通过链表中的 引用链接 次序实现的 。

?1.链表的实现

链表结构有三种情况，可以相互组合共八种链表结构。

1. 单向或双向
2. 带头或不带头（头结点一般装链表长度信息）
3. 循环或非循环

下面是无头单向非循环链表的实现：

public class MyLinkedList {
    class LinkedNode{
        int val;
        LinkedNode next;
        public LinkedNode(int val){
            this.val=val;
        }
    }
    LinkedNode head;

    // 1、无头单向非循环链表实现
        //头插法
        public void addFirst(int data){
        if(head==null){
            head.val=data;
        }else{
        LinkedNode node=new LinkedNode(data);
        node.next=head;
        head=node;
        }
        }
        //尾插法
        public void addLast(int data){
            LinkedNode cur=head;
            if(head==null){
                head.val=data;
            }else{
            while (cur.next!=null){
                cur=cur.next;
            }
            LinkedNode node=new LinkedNode(data);
            cur.next=node;
        }
        }
        //任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index,int data){
            LinkedNode cur=head;
            if(head==null){
                head.val=data;
            }else{
                if(index<1||index>size()){
                    System.out.println("插入位置不合法");
                }else{
                    index--;
                    while (index>0){
                        cur=cur.next;
                        index--;
                    }
                    LinkedNode node=new LinkedNode(data);
                    node.next=cur;
                    if(index==1){
                        head=node;
                    }
                }
            }
        }
        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key){
            LinkedNode cur=head;
            if(head==null){
                return false;
            }else{
            while (cur.next!=null){
                if(cur.val==key){
                    return true;
                }
                cur=cur.next;
            }
                if(cur.val==key){
                    return true;
                }
            return false;
        }
        }
        //删除第一次出现关键字为key的节点
        public void remove(int key){
            if(head!=null){
                if(head.val==key){
                    head=head.next;
                    return;
                }
                LinkedNode cur=head.next;
                LinkedNode prev=head;
            while (cur!=null&&cur.next!=null){
                if(cur.val==key){
                    prev.next=cur.next;
                    return;
                }
                cur=cur.next;
                prev=prev.next;
            }
                System.out.println("沒有要刪除的元素");
            }
        }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        if(head!=null){
            if(head.val==key){
                head=head.next;
            }
            LinkedNode cur=head.next;
            LinkedNode prev=head;
            while (cur!=null&&cur.next!=null){
                if(cur.val==key){
                    prev.next=cur.next;
                }
                cur=cur.next;
                prev=prev.next;
            }
            System.out.println("沒有要刪除的元素");
        }
        }
    //得到单链表的长度
    public int size(){
            LinkedNode cur=head;
            int num=0;
            while (cur!=null){
                num++;
                cur=cur.next;
            }
        return num;
    }
    public void clear() {
            LinkedNode cur;
            while (head!=null){
                cur=head;
                head=head.next;
                cur.val=0;
                cur.next=null;
            }
    }
    //遍历
    public void display() {
            LinkedNode cur=head;
            while (cur!=null){
                System.out.print(cur.val+"\t");
                cur=cur.next;
            }
    }
}

2.LinkedList的使用

Java中的linked是一个双向链表，且实现了 Deque，Cloneable，Serializable 三个接口。这说明该数据结构支持队列，克隆和序列化操作的。与 ArrayList 一样，允许 null 元素的存在，且是不支持多线程的。一些常见方法如下：

3.ArrayList和LinkedList的区别

4.链表OJ题训练

下面给出牛客或者力扣的经典题型，重复练习对加深知识点很有帮助

1. 反转一个单链表。
2. 链表的回文结构。
3. 输入两个链表，找出它们的第一个公共结点。
4. 给定一个链表，判断链表中是否有环。
5. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回?NULL