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

小皮侠

发布于 2024-04-08 20:40:48

700

发布于 2024-04-08 20:40:48

链表和LinkedList

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

1.链表的实现

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

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

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

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 元素的存在，且是不支持多线程的。一些常见方法如下：

方法	解释
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 位置元素设置为 e
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