1. AI技术聚合首页
  2. IT

顺序表和链表

社会演员多 • • IT • 阅读 48

导言：

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列…线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。而线性表有两种非常重要的结构，顺序表和链表。本篇文章主要对顺序表和链表的简单实现以及java中与之对应的集合进行一个介绍。

目录

正文：

一.顺序表

1.概念：

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

2.顺序表的特点：
  • 随机访问：由于顺序表的存储结构是连续的，因此可以通过下标直接访问任意位置的元素，时间复杂度为O(1)。
  • 插入和删除操作效率较低：在顺序表中，如果需要在中间位置插入或删除元素，需要将插入位置之后的所有元素依次向后移动或向前移动，时间复杂度为O(n)。
  • 动态扩容：由于数组的大小是固定的，当顺序表需要存储的元素数量超过数组的容量时，需要进行动态扩容操作，通常是创建一个新的更大的数组，并将原数组中的元素复制到新数组中。
3.顺序表的自实现：
import java.util.Arrays;

public class MyArrayList<T> {  //利用泛型创建类
    //顺序表的默认值
    private static final int DEFAULT_CAPACITY = 10;
    //可以接收所有类型的数组
    private Object[] array;
    //顺序表中实际存储值的个数
    private int size;

    public MyArrayList() {
        //构造函数，初始化数组的大小
        array = new Object[DEFAULT_CAPACITY];
        size = 0;
    }

    public void add(T element) {
        //判断顺序表是否满了
        if (size == array.length) {
            ensureCapacity();
        }
        array[size++] = element;
    }

    public void add(int index, T element) {
        //保证index合法
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        //判断是否满了
        if (size == array.length) {
            ensureCapacity();
        }
        //在顺序表中的指定位置插入元素时，腾出位置给新的元素。
        System.arraycopy(array, index, array, index + 1, size - index);

        array[index] = element;
        size++;
    }

    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        return (T) array[index];
    }

    public void remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            //在删除指定位置的元素后，通过将该位置后的元素向前移动一个位置，来保持顺序表的顺序。
            System.arraycopy(array, index + 1, array, index, numMoved);
        }
        array[--size] = null;
    }

    private void ensureCapacity() {
        //扩容1.5倍
        int newCapacity = array.length + array.length >> 1;
        array = Arrays.copyOf(array, newCapacity);
    }

    public int size() {
        return size;
    }

    public void set(int index, T element) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        array[index] = element;
    }


    public static void main(String[] args) {
        MyArrayList<String> myArrayList = new MyArrayList<>();

        // 添加元素
        myArrayList.add("aaa");
        myArrayList.add("bbb");
        myArrayList.add("bbb");
        myArrayList.add("ccc");
        myArrayList.add("ccc");

        myArrayList.add(0,"fff");

        // 获取元素
        System.out.println("未修改前下标为1的元素为: " + myArrayList.get(1));

        // 修改元素
        myArrayList.set(1, "ddd");

        // 删除元素
        myArrayList.remove(5);

        // 打印所有元素
        for (int i = 0; i < myArrayList.size(); i++) {
            System.out.println("下标为" + i + "的元素为: " + myArrayList.get(i));
        }
    }
}

运行结果为：

这个自实现的顺序表使用泛型，因此可以存储任意类型的元素。它提供了添加、获取、修改和删除元素的基本操作，并在需要时动态调整底层数组的大小。 

4.java中对应的集合：

在 Java 中，顺序表对应的集合是 ArrayList。ArrayList 是 Java 中的一个动态数组实现的类，可以根据需要动态地增加或减少大小，因此非常适合作为顺序表的数据结构。ArrayList 实现了 List 接口，可以根据索引快速访问元素，并支持添加、删除、获取元素等操作。因此，可以使用 ArrayList 来实现顺序表的功能。

下面是一些 ArrayList 的详细介绍：

  • 动态数组实现：ArrayList 内部使用数组来存储元素，它可以根据需要动态地增加或减少数组的大小，因此可以灵活地存储任意数量的元素。

  • 实现了List接口：ArrayList 实现了 List 接口，因此它支持列表的相关操作，比如添加、删除、获取元素等。同时，它也支持索引访问，可以通过索引快速访问列表中的元素。

  • 自动扩容：当向 ArrayList 中添加元素时，如果当前的容量不足，ArrayList 会自动进行扩容，通常会扩大为原来的 1.5 倍大小，以减少频繁扩容的开销。

  • 不是线程安全的：ArrayList 不是线程安全的，如果需要在多线程环境中使用，需要手动进行同步处理，或者使用 Collections.synchronizedList 方法来获取一个线程安全的列表。

  • 支持泛型：ArrayList 支持泛型，可以指定存储的元素类型，避免了在获取元素时需要进行类型转换。

  • 元素可以为null：ArrayList 中可以存储 null 元素。

ArrayList 中包含了丰富的方法，用于添加、删除、获取元素，以及其他操作。下面是 ArrayList 中常用的方法的详细介绍：

1.添加元素：

  • add(E e)：在列表的末尾添加指定的元素。
  • add(int index, E element)：在指定的位置插入指定的元素，原位置上的元素以及后续元素向右移动。

2.获取元素：

  • get(int index)：返回列表中指定位置的元素。
  • indexOf(Object o)：返回指定元素在列表中第一次出现的位置索引，如果不存在则返回 -1。
  • lastIndexOf(Object o)：返回指定元素在列表中最后一次出现的位置索引，如果不存在则返回 -1。

3.删除元素：

  • remove(int index)：移除列表中指定位置的元素，后续元素向左移动。
  • remove(Object o)：移除列表中第一次出现的指定元素。
  • clear()：移除列表中的所有元素。

4.替换元素：

  • set(int index, E element)：用指定的元素替换列表中指定位置的元素。

5.判断元素是否存在：

  • contains(Object o)：如果列表中包含指定的元素，则返回 true。
  • isEmpty()：如果列表不包含任何元素，则返回 true。

6.获取列表大小：

  • size()：返回列表中的元素个数。

7.转换为数组：

  • toArray()：将列表转换为一个数组。

8.迭代：

  • iterator()：返回一个迭代器，用于遍历列表中的元素。

以上是 ArrayList 中的一些常用方法，它们提供了丰富的功能，可以用于对列表中的元素进行添加、删除、获取等操作。通过这些方法，可以方便地操作 ArrayList 中的元素，实现各种常见的列表操作。

使用案例：

import java.util.ArrayList;

public class test {
    public static void main(String[] args) {
        ArrayList<String> arrayList = new ArrayList<>();

        // 添加元素
       arrayList.add("aaa");
       arrayList.add("bbb");
       arrayList.add("bbb");
       arrayList.add("ccc");
       arrayList.add("ccc");

       arrayList.add(0, "fff");

        // 获取元素
        System.out.println("未修改前下标为1的元素为: " + arrayList.get(1));

        // 修改元素
       arrayList.set(1, "ddd");

        // 删除元素
        arrayList.remove(5);

        // 打印所有元素
        for (int i = 0; i < arrayList.size(); i++) {
            System.out.println("下标为" + i + "的元素为: " + arrayList.get(i));
        }
    }
}

运行结果：

 

5.小结：

顺序表由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。顺序表主要适用于需要频繁访问、插入、删除元素，并且需要动态管理大小的场景。

二.链表

1.概念：

链表解决了顺序表移动元素时时间复杂度较高的缺点，它由一系列节点组成，每个节点包含数据元素和一个指向下一个节点的引用。链表中的元素按照其在内存中的实际顺序进行连接，而不需要像数组那样在内存中连续存储。这使得链表对于插入和删除操作非常高效，但是访问元素需要遍历整个链表，因此对于随机访问来说效率较低。

链表可以分为单向链表、双向链表和循环链表三种基本类型。

  1. 单向链表：单向链表中，每个节点只包含一个指向下一个节点的引用。单向链表的优点是结构简单，占用的存储空间小，但是访问元素时需要从头节点开始遍历，效率较低。

  2. 双向链表：双向链表中，每个节点包含一个指向下一个节点的引用和一个指向上一个节点的引用。双向链表可以支持双向遍历，因此在某些场景下可以提高访问效率。

  3. 循环链表：循环链表是一种特殊的链表，其中最后一个节点指向第一个节点，形成一个循环。循环链表常用于需要循环访问的场景，例如循环队列。

链表的常见操作包括插入、删除、查找等，通常使用指针来实现这些操作。链表在内存中的存储方式使得它可以动态地分配内存空间，因此适用于需要频繁进行插入和删除操作的场景。然而，链表的随机访问效率较低，因此在需要频繁进行随机访问的场景下，可能不是最佳选择。

2.链表的特点：

  • 动态内存分配：链表的节点是动态分配的，可以根据需要动态地分配和释放内存空间。这使得链表在插入和删除操作时更加高效，因为不需要提前分配固定大小的内存空间。

  • 非连续存储：链表中的节点在内存中并不是连续存储的，而是通过指针相互连接。这使得链表可以更灵活地存储数据，但也导致了链表在访问元素时可能需要遍历整个链表，因此访问效率较低。

  • 插入和删除效率高：由于链表的节点是动态分配的，并且插入和删除操作只需要修改指针的指向，所以链表在插入和删除操作上具有较高的效率。

  • 查找效率低：由于链表中的节点并不是连续存储的，所以在查找特定元素时，可能需要从头开始遍历整个链表，导致查找效率较低。

  • 多种类型：链表可以分为单向链表、双向链表和循环链表等多种类型，每种类型都有自己的特点和适用场景。

3.自实现：
import java.util.LinkedList;

public class MyLinkedList<T> {
    private Node head;  // 链表头节点
    private int size;    // 链表的元素数量

    private class Node {
        T data;           // 节点数据
        Node next;        // 下一个节点的引用

        Node(T data) {
            this.data = data;
            this.next = null;
        }
    }

    public MyLinkedList() {
        this.head = null;
        this.size = 0;
    }

    // 添加元素到链表末尾
    public void add(T element) {
        Node newNode = new Node(element);
        if (head == null) {
            head = newNode;  // 如果链表为空，新节点成为头节点
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;  // 将新节点连接到链表末尾
        }
        size++;
    }
    // 在指定位置插入元素
    public void add(int index, T element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }

        Node newNode = new Node(element);
        if (index == 0) {
            newNode.next = head;
            head = newNode;  // 如果在头部插入，新节点成为头节点
        } else {
            Node current = head;
            for (int i = 0; i < index - 1; i++) {
                current = current.next;
            }
            newNode.next = current.next;
            current.next = newNode;  // 在指定位置插入新节点
        }
        size++;
    }

    // 获取指定位置的元素
    public T get(int index) {
        checkIndex(index);
        Node current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.data;
    }

    // 修改指定位置的元素
    public void set(int index, T element) {
        checkIndex(index);
        Node current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        current.data = element;
    }

    // 删除指定位置的元素
    public void remove(int index) {
        checkIndex(index);
        if (index == 0) {
            head = head.next;  // 如果删除头节点，直接将头指针指向下一个节点
        } else {
            Node current = head;
            for (int i = 0; i < index - 1; i++) {
                current = current.next;
            }
            current.next = current.next.next;  // 将当前节点的下一个节点指向下下个节点，实现删除
        }
        size--;
    }

    // 获取链表的元素数量
    public int size() {
        return size;
    }

    // 检查索引是否合法
    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }

    public static void main(String[] args) {
        MyLinkedList<String> myLinkedList = new MyLinkedList<>();

        // 添加元素
        myLinkedList.add("aaa");
        myLinkedList.add("bbb");
        myLinkedList.add("ccc");
        myLinkedList.add("ccc");
        myLinkedList.add(0,"fff");

        // 获取元素
        System.out.println("修改前下标为1的元素为: " + myLinkedList.get(1));

        // 修改元素
        myLinkedList.set(1, "ccc");

        // 删除元素
        myLinkedList.remove(4);

        // 打印所有元素
        for (int i = 0; i < myLinkedList.size(); i++) {
            System.out.println("下标为 " + i + "的元素为: " + myLinkedList.get(i));
        }
    }
}

运行结果为：

这个简单的单向链表实现包括链表节点 Node 和链表类 MyLinkedList。它支持添加、获取、修改和删除元素等基本操作。

4.java中对应的集合：

在Java中，链表对应的集合主要有LinkedList和LinkedHashSet。这里主要介绍LinkedList。

LinkedList是 Java 中集合框架中的一个实现类，实现了双向链表数据结构。与 ArrayList 不同，LinkedList`不是基于数组实现的，而是通过节点之间的引用来构建链表。每个节点包含一个数据元素和两个引用，分别指向前一个节点（前驱节点）和后一个节点（后继节点）。由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高

详细介绍：

1. 双向链表结构： 每个节点都有两个引用，指向前一个节点和后一个节点，形成一个双向链表。

2. 不连续的内存空间： 由于是链表结构，不需要像 ArrayList那样在内存中分配一块连续的空间。

3. 灵活的插入和删除： 插入和删除元素的操作相对于 ArrayList 更加高效，因为只需要调整节点的引用。

4. 支持 null 元素：LinkedList允许存储 null 元素。

5. 不支持随机访问：LinkedList的访问是基于节点的引用遍历，因此随机访问效率较低，时间复杂度为 O(n)。

主要方法和操作：

1. 添加元素：

  • addFirst(E element): 在链表的开头添加元素。
  • addLast(E element): 在链表的末尾添加元素。
  • add(int index, E element): 在指定位置插入元素。

2. 获取元素：

  • getFirst(): 获取链表的第一个元素。
  • getLast(): 获取链表的最后一个元素。
  • get(int index): 获取指定位置的元素。

 3. 删除元素：

  •    removeFirst():删除链表的第一个元素。
  •    removeLast():删除链表的最后一个元素。
  •    remove(int index):删除指定位置的元素。

4. 修改元素：

  • set(int index, E element): 修改指定位置的元素。

5. 遍历元素：

  • forEach(Consumer<? super E> action): 使用给定的操作对每个元素执行操作。

6. 其他方法：

  • size(): 返回链表的元素个数。
  • isEmpty(): 判断链表是否为空。

使用案例：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class test {
    public static void main(String[] args) {

        // 创建一个LinkedList对象
        LinkedList<String> linkedList = new LinkedList<>();

        // 向链表中添加元素
       linkedList.add("aaa");
       linkedList.add("bbb");
       linkedList.add("ccc");
       linkedList.add("ccc");
       linkedList.add(0, "fff");

        // 遍历链表并打印元素
        System.out.println("Elements in the linked list:");
        for (String fruit : linkedList) {
            System.out.println(fruit);
        }

        // 获取元素
        System.out.println("修改前下标为1的元素为: " + linkedList.get(1));

        // 修改元素
       linkedList.set(1, "ccc");

        // 删除元素
       linkedList.remove(4);

        // 打印所有元素
        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println("下标为 " + i + "的元素为: " + linkedList.get(i));
        }
    }
}

 

5.小结：

链表适合频繁进行插入和删除操作的场景，但在需要频繁查找元素的场景下效率较低。链表的灵活性使得它在某些特定场景下具有重要的作用，例如实现队列、栈等数据结构，或者作为其他数据结构的基础组件。

总结：

顺序表和链表是两种常见的数据结构，并没有什么优劣之分，它们各自具有特定的特点和适用场景。顺序表适合对元素的随机访问较多的场景，而链表适合频繁进行插入和删除操作的场景。在实际应用中，可以根据具体的需求和操作特点选择合适的数据结构。

文章出处登录后可见！

已经登录？立即刷新

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
社会演员多的头像社会演员多普通用户
0
上一篇 2023年12月15日
下一篇 2023年12月15日

相关推荐