顺序表(Arraylist)和链表(Linkedlist)

发布于：2025-04-17 ⋅ 阅读:(30) ⋅ 点赞:(0)

List

List是一个接口，继承自Collection。

从数据结构角度来说，List就是一个线性表，即用n个相同类型的有限序列，可以在此序列中可以进行增删改查操作。

List是接口不能直接实例化，Linkedlist和Arraylist都实现了List。

Arraylist

顺序表(Arraylist)是用一段物理地址连续的存储单元进行存储元素的线性结构，一般用数组进行实现，在数组上进行增删改查。

1.ArrayList是以泛型的方式实现的，使用时必须要先实例化。
2.ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问。
3.ArrayList实现了Cloneable接口，表明ArrayList可以clone。
4.ArrayList底层是一段连续的空间，并且可以动态扩容。

Arraylist使用

public static void main(String[] args) {
// ArrayList创建，推荐写法
// 构造⼀个空的列表
List<Integer> list1 = new ArrayList<>();

// 构造⼀个具有10个容量的列表
List<Integer> list2 = new ArrayList<>(10);
list2.add(1);
list2.add(2);
list2.add(3);
// list2.add("hello"); // 编译失败，List<Integer>已经限定了，list2中只能存储整
形元素
// list3构造好之后，与list中的元素⼀致
ArrayList<Integer> list3 = new ArrayList<>(list2);
// 避免省略类型，否则：任意类型的元素都可以存放
List list4 = new ArrayList();
list4.add("111");
list4.add(100);
}

Arraylist常见操作

public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("JavaSE");
list.add("JavaWeb");
list.add("JavaEE");
list.add("JVM");
list.add("测试课程");
System.out.println(list);

// 获取list中有效元素个数
System.out.println(list.size());

// 获取和设置index位置上的元素，注意index必须介于[0, size)间
System.out.println(list.get(1));
list.set(1, "JavaWEB");
System.out.println(list.get(1));

// 在list的index位置插⼊指定元素，index及后续的元素统⼀往后搬移⼀个位置
list.add(1, "Java数据结构");
System.out.println(list);

// 删除指定元素，找到了就删除，该元素之后的元素统⼀往前搬移⼀个位置
list.remove("JVM");
System.out.println(list);

// 删除list中index位置上的元素，注意index不要超过list中有效元素个数,否则会抛出下标
越界异常
list.remove(list.size()-1);
System.out.println(list);

// 检测list中是否包含指定元素，包含返回true，否则返回false
if(list.contains("测试课程")){
list.add("测试课程");
}

// 查找指定元素第⼀次出现的位置：indexOf从前往后找，lastIndexOf从后往前找
list.add("JavaSE");
System.out.println(list.indexOf("JavaSE"));
System.out.println(list.lastIndexOf("JavaSE"));

// 使⽤list中[0, 4)之间的元素构成⼀个新的SubList返回,但是和ArrayList共⽤⼀个
elementData数组
List<String> ret = list.subList(0, 4);
System.out.println(ret);
list.clear();
System.out.println(list.size());
}

ArrayList遍历

public static void main(String[] args) {
            Arraylistoj i = new Arraylistoj();
            i.generate(10);
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        for (int j = 0;j< list.size();j++){
            System.out.println(list.get(j));
        }
        for (int value:list) {
            System.out.println(value);
        }
       Iterator<Integer> lo = list.iterator();
        while(lo.hasNext()){
            System.out.println(lo.next());
        }
    }

模拟实现Arraylist

public class myArraylist {
    public int [] arr = new int[10];
    public int size;

    public myArraylist(int j){
        if(j>=10){
            this.arr = new int[j];
        }
    }
    public void add(int value) {
        if (size >= arr.length) {
            resize();
        }
        arr[size] = value;
        size++;
    }
    public void resize(){
        int[] newarr = new int[arr.length*2];
        for (int i = 0; i < size; i++) {
            newarr[i] = arr[i];
        }
        arr = newarr;
    }
    public void add(int index,int value){
        if(index<0||index>size){
            return;
        }
        if(size >= arr.length){
            resize();
        }
        for (int i = size-1; i >= index ; i--) {
            arr[i+1] = arr[i];
        }
        arr[index] = value;
        size++;

    }
    public void remove(int index){
        if(index<0||index>=size){
            throw new RuntimeException();
        }
        for (int i = index; i < size-1; i++) {
            arr[i] = arr[i+1];
        }
        size--;
    }
    public Boolean remove1(int value){
        int i = 0;
        for ( ;i < size; i++) {
            if(arr[i] == value){
                break;
            }
        }
        if(arr[i] == value){
            for (int j = i; j < size-1; j++) {
                arr[j] = arr[j+1];
            }
        }else{
            return false;
        }
        size--;
        return true;
    }
    public int get(int index){
        if(index<0||index>=size){
            throw new RuntimeException();
        }
        return arr[index];
    }
    public void set(int index,int values){
        if(index<0||index>=size){
            throw new RuntimeException();
        }
        arr[index] = values;
    }
    public void clean(){
        size=0;
    }
    public Boolean contins(int value){
        for (int i = 0; i < size; i++) {
            if(arr[i]==value){
                return true;
            }
        }
        return false;
    }
    public List<Integer> sublist(int left, int right){
        if(left<0||right>size){
            throw new RuntimeException();
        }
        ArrayList<Integer> l = new ArrayList<>();

        for (int i = left; i < right; i++) {
            l.add(arr[i]);
        }
        return l;
    }

    @Override
    public String toString() {
        StringBuilder i = new StringBuilder();
        i.append("[");
        for (int j = 0; j < size; j++) {
            i.append(arr[j]);
            if(j<size-1){
                i.append(",");
            }
        }
        i.append("]");
        return i.toString();
    }

Linkedlist

ArrayList的缺陷

ArrayList在进行任意位置删除和插入元素，就需要将元素整体向后或向前移动，时间复杂度为O(n)，因此Arraylist不适合进行插入或删除元素比较多的时候。

链表

为解决上述问题，引入Linkedlist，链表是物理存储结构非连续的存储结构，逻辑上链表是通过链表引用链接连接的。

链表在逻辑上看是连续的，但在物理结构上并非连续。

节点一般从堆上申请的，从堆上申请的节点是按一定策略，可能连续，可能不连续。

链表的结构有多种：双向和单向，带头和非带头，循环和非循环。

链表的模拟实现

class Node{
   public int val;
   public Node next = null;


    public Node(int val) {
        this.val = val;

    }
}
    public class myLinklist {
    public Node head = null;
    public int size;
    public void addfirst(int value){
        Node newnode = new Node(value);
        newnode.next = head;
        head = newnode;
        size++;
    }
    public void addlist(int value){
        if(head==null){
            addfirst(value);
            return;
        }
        Node node = new Node(value);
        Node cur = head;
       for (;cur!=null;cur = cur.next){
           if(cur.next == null){
               break;
           }
       }
        cur.next = node;
        node.next = null;
        size++;
    }
    public void add(int index,int value){
        if(index<0||index>size){
            return;
        }
        if(index==size){
            addlist(value);
            size++;
            return;
        }
        if(index==0){
            addfirst(value);
            size++;
            return;
        }
        Node node = head;
        Node newnode = new Node(value);
        for (int i = 0; i < index-1; i++) {
        node = node.next;
        }
        newnode.next = node.next;
        node.next = newnode;
        size++;
    }
    public Boolean contins(int valus){
        Node node = head;
        for (;node!=null;node = node.next){
            if(node.val==valus){
                return true;
            }
        }
        return false;
    }
    public void remove(int index,int value){
        if(index<0||index>=size){
            return;
        }
        if(index==0){
            head=head.next;
            size--;
            return;
        }
        Node cur = head;
        Node pre = null;
        for (int i = 0; i < index; i++) {
            pre = cur;
            cur = cur.next;
        }
        pre.next = cur.next;
        size--;
    }
    public void remove(int curnode){
        if(head==null){
            return;
        }
        if(head.val==curnode){
            head = head.next;
            size--;
            return;
        }
        Node cur = head;
        Node prv = null;
        for (;cur!=null;){
            if(cur.val==curnode){
                break;
            }
            prv = cur;
            cur = cur.next;
        }
        prv.next = cur.next;
        size--;
    }
    public int indexOf(int value){
        Node node = head;
        int k = 0;
        for (;node!=null;node = node.next){
            if(node.val==value){
                return k;
            }
            k++;
        }
        return -1;
    }
    public void clean(){
        head = null;
    }

        @Override
        public String toString() {
         StringBuilder o = new StringBuilder();
         o.append("[");
         Node i = head;
         for (;i!=null;i = i.next) {
                o.append(i.val);
                o.append(" ");
                if(i.next != null){
                    o.append(",");
                }
            }
         o.append("]");
            return o.toString();
        }

Linkedlist介绍

Linkedlist实现了List。

Linkedlist的底层是双向链表。

Linkedlist没实现RandomAccess接口，表明不支持随机访问。

Linkedlist在随机插入和删除时，时间复杂度为O(1)。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布