三、java线性表（顺序表、链表、栈、队列）

三、线性表

线性表是一种经典的数据结构，它遵循线性逻辑结构的特点。

在Java中，线性表主要通过ArrayList和LinkedList来实现。

1.特点：

• 数据元素之间具有“一对一”的逻辑关系

• 第一个数据元素没有前驱，这个数据元素被称为头结点

• 最后一个数据元素没有后继，这个数据元素被称为尾节点

• 除了第一个数据元素和最后一个数据元素外，其余的数据元素有且仅有唯一前驱和后继

   前驱元素：若元素A在B元素的前面，则A为B的前驱元素后继元素：若元素B在元素A的后面，则B为A的后继元素
  

2.ArrayList：

• ArrayList是Java中实现线性表的一种方式，采用顺序存储结构。

• 优点：访问速度快，支持动态扩展。

• 缺点：插入和删除操作相对较慢。

  应用场景：适用于查找和访问操作较频繁的场景，如统计数据、存储用户信息等。
  

3.LinkedList：

• LinkedList是Java中实现线性表的另一种方式，采用链式存储结构。

• 优点：插入和删除操作快，支持动态扩展。

• 缺点：访问速度相对较慢。

   应用场景：适用于插入和删除操作较频繁的场景，如队列、栈等。
  

4.线性表的分类

线性表中的数据存储的方式可以是顺序存储，也可以是链式存储

按照数据的存储方式的不同，可以把线性表分为：

• 顺序表
• 链表

5.线性表的应用：

• 排序：线性表可以用于实现各种排序算法，如冒泡排序、快速排序等。

• 查找：线性表可以用于实现查找算法，如顺序查找、二分查找等。

• 队列：线性表可以用于实现队列数据结构，遵循“先进先出”（FIFO）的原则。

• 栈：线性表可以用于实现栈数据结构，遵循“后进先出”（LIFO）的原则。

1.1 顺序表

顺序表的特点是元素在内存中是连续存储的，可以通过索引进行快速的访问。

在 Java 中，顺序表是一种线性表的实现方式，它通过使用数组来存储元素，并按照元素在数组中的位置来建立元素之间的逻辑关系。

在 Java 中，常用的顺序表实现方式是使用 ArrayList 类。ArrayList 是 Java 集合框架中的一员，它实现了动态数组，可以在运行时自动调整大小。以下是对顺序表在 Java 中的使用和特点的详细讲解：

1.1.1 创建顺序表

可以通过实例化 ArrayList 类来创建一个顺序表。例如：

ArrayList<String> list = new ArrayList<>();

	在这个例子中，我们创建了一个名为 `list` 的顺序表，其中存储的元素类型是 String。

1.1.2. 添加元素

可以使用 add 方法向顺序表中添加元素。例如：

list.add("element1");
list.add("element2");

	  在上述代码中，我们向顺序表 `list` 中添加了两个元素。

1.1.3. 访问元素

顺序表中的元素可以通过索引来访问。索引从0开始，表示第一个元素。例如：

String element = list.get(0);

	这个例子中，我们使用 `get` 方法来获取顺序表 `list` 中索引为 0 的元素。

1.1.4. 删除元素

可以使用 remove 方法删除顺序表中的元素。例如：

list.remove(0);

	 这个例子中，我们删除了顺序表 `list` 中索引为 0 的元素。

1.1.5. 修改元素

通过索引可以修改顺序表中的元素。例如：

list.set(0, "newElement");

	 这个例子中，我们将顺序表 `list` 中索引为 0 的元素修改为 "newElement"。

1.1.6. 其他常用操作

• 获取顺序表的大小：可以使用 size 方法来获取顺序表中元素的个数。

• 遍历顺序表：可以使用循环结构（如 for-each 循环）来遍历顺序表中的所有元素。

• 判断顺序表是否为空：可以使用 isEmpty 方法来判断顺序表是否为空。

import java.util.Arrays;class ArrayList {private int size;private int[] elements;private static final int DEFAULT_CAPACITY = 10;public ArrayList() {this.elements = new int[DEFAULT_CAPACITY];this.size = 0;}// 在尾部插入元素public void add(int value) {ensureCapacity(size + 1);elements[size++] = value;}// 在指定位置插入元素public void add(int index, int value) {ensureCapacity(size + 1);if (index < 0 || index > size) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}System.arraycopy(elements, index, elements, index + 1, size - index);elements[index] = value;size++;}// 获取指定位置的元素public int get(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}return elements[index];}// 修改指定位置的元素public void set(int index, int value) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}elements[index] = value;}// 删除指定位置的元素public void remove(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}System.arraycopy(elements, index + 1, elements, index, size - index - 1);size--;}// 清空顺序表public void clear() {elements = new int[DEFAULT_CAPACITY];size = 0;}// 获取顺序表的长度public int size() {return size;}// 确保容量大小private void ensureCapacity(int capacity) {if (capacity > elements.length) {int newCapacity = elements.length + (elements.length >> 1);elements = Arrays.copyOf(elements, newCapacity);}}
}// 测试顺序表的代码实现
public class Main {public static void main(String[] args) {ArrayList list = new ArrayList();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);System.out.println("顺序表的元素：");for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}System.out.println();list.remove(2);list.set(1, 6);System.out.println("删除元素后，修改元素后的顺序表：");for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}System.out.println();}
}

在上面的代码中，我们首先定义了一个顺序表类 ArrayList，其中包含一个动态数组 elements 和当前元素个数 size。
该类提供了以下功能：在尾部插入元素的方法 add在指定位置插入元素的方法 add获取指定位置的元素的方法 get修改指定位置的元素的方法 set删除指定位置的元素的方法 remove清空顺序表的方法 clear获取顺序表的长度的方法 size
其中，为了保证顺序表的容量足够，我们使用了 ensureCapacity 方法来保证容量大小。	
最后，在 Main 类中，我们创建了一个顺序表对象 list，并进行了插入、删除、修改等操作，并最终打印出顺序表的元素。

1.1.7. 动态扩容

   顺序表最大的优点是支持随机访问，但其缺点是一旦初始化大小之后再扩容就需要重新拷贝内存，会浪费大量时间。
为了解决这个问题，Java中的 ArrayList 实现了动态扩容的机制，即在容量不足时自动增加内部数组的大小						以容纳更多元素。这样可以避免因频繁拷贝内存而导致时间浪费的问题。

1.1.8. 规定类型

	ArrayList 在实例化时需要指定列表中元素的类型，这个类型可以是Java中的任何类型，例如 String、Integer、Object 等等。

这个实现方式使得 ArrayList 可以保证存储的元素类型和顺序的一致性。

1.1.9. 基于接口的设计

	 ArrayList 实现了 List 接口，这个接口是 Java 集合框架中的一员。

这种基于接口的设计模式允许开发人员在更高的抽象级别上编程，而不是关注具体实现细节。

1.1.10. 线程不安全

	ArrayList 是非线程安全的，即多个线程并发访问 ArrayList 时，可能会导致数据不一致等问题。为了解决线程不安全的问题，Java 中提供了线程安全的 ArrayList 实现方式，即 Vector 类。Vector 类提供了和 ArrayList 类似的方法，但它是线程安全的，但是其效率比 ArrayList 要低。

1.2 链表

链表由一系列的节点（Node）组成，每个节点包含存储的数据以及一个指向下一个节点的引用。

与数组相比，链表在插入和删除元素时更为高效，但访问特定位置的元素需要遍历整个链表。

Java中常见的链表实现方式有单向链表（Singly Linked List）和双向链表（Doubly Linked List）。

1.2.1 单向链表（Singly Linked List）

单向链表的每个节点包括存储的数据和一个指向下一个节点的引用。最后一个节点的引用为空。

单向链表的优点是实现简单，每个节点只需要保存一个引用。

创建一个单向链表的基本步骤：

• 创建节点
• 设置节点的值
• 设置节点间的引用

public class SinglyLinkedList {private Node head;    // 链表头节点private class Node {int data;        // 节点数据Node next;       // 下一个节点public Node(int data) {this.data = data;this.next = null;}}// 在链表头插入节点public void push(int data) {Node newNode = new Node(data);newNode.next = head;head = newNode;}// 在链表尾部添加节点public void append(int data) {Node newNode = new Node(data);// 如果链表为空，将新节点设置为头节点if (head == null) {head = newNode;return;}Node current = head;// 找到链表最后一个节点while (current.next != null) {current = current.next;}// 将新节点插入到链表最后current.next = newNode;}// 在链表中插入节点public void insert(int data, int position) {Node newNode = new Node(data);// 如果链表为空，将新节点设置为头节点if (head == null) {head = newNode;return;}// 如果插入位置是头节点之前，则将新节点作为头节点if (position <= 0) {newNode.next = head;head = newNode;return;}Node current = head;int i = 1;// 找到插入位置的前一个节点while (current.next != null && i < position) {current = current.next;i++;}// 插入新节点Node temp = current.next;current.next = newNode;newNode.next = temp;}// 删除链表中指定数据的节点public void delete(int data) {if (head == null) {return;}// 处理头节点if (head.data == data) {head = head.next;return;}Node current = head;Node prev = null;// 遍历链表，查找指定数据的节点while (current != null) {if (current.data == data) {prev.next = current.next;return;}prev = current;current = current.next;}}// 打印链表中的所有节点public void printList() {if (head == null) {System.out.println("链表为空");return;}System.out.print("链表元素: ");Node current = head;while (current != null) {System.out.print(current.data + " ");current = current.next;}System.out.println();}public static void main(String[] args) {SinglyLinkedList sll = new SinglyLinkedList();sll.push(1);sll.append(2);sll.append(3);sll.printList();    // 输出：链表元素：1 2 3sll.insert(4, 1);sll.printList();    // 输出：链表元素：1 4 2 3sll.delete(2);sll.printList();    // 输出：链表元素：1 4 3}
}

1.2.2 双向链表（Doubly Linked List）

双向链表的每个节点包含存储的数据、一个指向下一个节点的引用以及一个指向前一个节点的引用。

双向链表的优点是可以从任意一个节点开始正向或反向遍历。双向链表相比单向链表需要额外的空间来存储前一个节点的引用。

在Java中，可以使用内置的 LinkedList 类来实现链表。

可以通过以下几种操作对链表进行操作：

• 添加元素：使用 add 方法在链表的末尾添加元素，或使用 addFirst 和 addLast 方法在链表的头部或尾部添加元素。

• 删除元素：使用 remove 方法按照元素的值或位置删除元素，或使用 removeFirst 和 removeLast 方法删除链表的头部或尾部元素。

• 获取元素：使用 get 方法按照索引获取链表中的元素，或使用 getFirst 和 getLast 方法获取链表的头部或尾部元素。

• 修改元素：使用 set 方法按照索引修改链表中的元素。

• 遍历链表：使用循环结构（如 for-each 循环）来遍历链表中的所有元素。

// 定义双链表的节点类
class Node {int data;Node prev;Node next;public Node(int data) {this.data = data;this.prev = null;this.next = null;}
}// 定义双链表类
class DoublyLinkedList {private Node head;public DoublyLinkedList() {this.head = null;}// 在链表头部插入节点public void insertAtHead(int data) {Node newNode = new Node(data);if (head == null) {head = newNode;} else {head.prev = newNode;newNode.next = head;head = newNode;}}// 在链表尾部插入节点public void insertAtTail(int data) {Node newNode = new Node(data);if (head == null) {head = newNode;} else {Node current = head;while (current.next != null) {current = current.next;}current.next = newNode;newNode.prev = current;}}// 打印链表元素public void printList() {Node current = head;System.out.print("双链表的元素：");while (current != null) {System.out.print(current.data + " ");current = current.next;}System.out.println();}
}// 测试双链表的代码实现
public class Main {public static void main(String[] args) {DoublyLinkedList list = new DoublyLinkedList();list.insertAtHead(3);list.insertAtHead(2);list.insertAtHead(1);list.insertAtTail(4);list.insertAtTail(5);list.printList();}
}

1.3 LinkedList VS ArrayList

LinkedList 和 ArrayList 是 Java 中常用的两种列表实现方式，它们的内部实现和使用方式有所不同。

1.3.1 内部实现

• LinkedList 通过节点之间的引用连接来实现链表。每个节点都包含存储的元素以及指向前一个节点和后一个节点的引用。
• ArrayList 内部使用动态数组来存储元素。当元素数量超过当前数组容量时，ArrayList 会自动增加内部数组的大小。

1.3.2 插入和删除操作

• 在索引位置进行插入和删除操作时，LinkedList 有着更好的性能，因为它只需要调整节点之间的引用即可。

• ArrayList 需要移动后面的元素来保持一致的顺序。

1.3.3 随机访问操作

• 由于 ArrayList 使用基于数组的实现，它支持通过索引进行高效的随机访问。
• LinkedList 需要从头节点开始遍历，直到遇到目标索引位置。

1.3.4 内存占用

• LinkedList 需要为每个节点额外存储前后节点的引用，所以在相同数量元素的情况下，它通常会占用更多的内存。
• ArrayList 则只需存储元素本身。

1.3.5 迭代器遍历

• 无论是 LinkedList 还是 ArrayList 都可以通过迭代器（Iterator）来遍历列表。

1.3.6 总结

• 如果需要频繁进行插入和删除操作，可以考虑使用 LinkedList。

• 如果需要快速的随机访问和较低的内存消耗，可以使用 ArrayList。

1.3.7 使用 LinkedList 的场景

1.3.7.1 使用场景
LinkedList 在以下场景中可能更加适用：

• 频繁的插入和删除操作

  由于 LinkedList 的插入和删除操作只需要调整节点之间的引用，所以在频繁进行插入和删除操作的场景下，LinkedList 通常比 ArrayList 更高效。

• 需要实现队列或栈的功能

  由于 LinkedList 的特点，它很容易实现队列（先进先出）或栈（后进先出）的功能。

   例如，可以使用 addFirst 和 removeFirst 方法在链表的头部进行插入和删除操作，从而实现栈的功能。
  

• 需要用作缓存或缓冲区

  LinkedList 可以方便地进行头部或尾部的添加和删除操作，这使得它非常适合用作缓存或缓冲区

   例如实现 LRU 缓存算法。
  

• 少量元素和迭代遍历

  相比 ArrayList，LinkedList 在内存占用上通常更高，所以当列表中的元素数量较少时，使用 LinkedList 可能更加合适。此外，LinkedList 可以通过迭代器进行遍历，适用于需要随机访问的场景。

1.3.7.2 注意事项

在使用 LinkedList 时，需要注意以下几点：

• 非线程安全

  LinkedList 不是线程安全的，如果需要在多线程环境中使用，需要进行适当的同步或使用线程安全的列表实现，如 Vector 或 CopyOnWriteArrayList。

• 内存占用

  由于需要为每个节点额外存储前后节点的引用，LinkedList 在相同数量元素的情况下可能会占用更多的内存。因此，当需要存储大量元素时需要注意内存消耗的问题。

• 遍历和随机访问操作

  相对于 ArrayList，LinkedList 的遍历和随机访问效率较低。如果需要快速地随机访问元素或遍历整个列表，请考虑使用其他的列表实现方式。

• 性能问题

  在实际的应用中，LinkedList 需要在空间和时间上权衡性能。在某些情况下，LinkedList 的性能可能不如其他的列表实现方式。因此，在选择使用 LinkedList 时，需要结合具体的应用场景和性能需求做出选择。

   总而言之，LinkedList 适用于频繁的插入和删除操作、实现队列或栈的功能、用作缓存或缓冲区等场景。当元素数量较少且需要迭代遍历时，也可以考虑使用 LinkedList。需要注意的是，LinkedList 是非线程安全的，如果在多线程环境中使用链表，需要进行适当的同步。
  

综上所述，Java中提供了内置的 LinkedList 类来实现链表。

链表适用于频繁的插入和删除操作，但访问特定位置的元素效率较低。

使用链表时，需要注意其线程安全性，并根据需要选择单向链表或双向链表的实现方式。

1.4 栈

在Java中，栈（Stack）是一种基于后进先出（LIFO）原则的数据结构。

它可以看作是一种特殊的线性表，只允许在表的一端进行插入和删除操作，这一端被称为栈顶。

Java中提供了栈的标准实现类，即java.util.Stack类。除了Stack类，还可以使用ArrayDeque类来实现栈的功能。

栈的主要特点：

1. 后进先出（LIFO）的原则：最后插入的元素首先被访问或删除。

2. 只允许在栈顶进行操作：栈的插入操作通常被称为推入（push），删除操作通常被称为弹出（pop）。

下面是使用Stack类实现栈的基本操作的示例代码：

import java.util.Stack;public class StackExample {public static void main(String[] args) {// 创建一个空栈Stack<Integer> stack = new Stack<>();// 推入元素到栈中stack.push(10);stack.push(20);stack.push(30);// 弹出栈顶元素int top = stack.pop();System.out.println("弹出的栈顶元素为：" + top);// 获取栈顶元素但不弹出int peekTop = stack.peek();System.out.println("当前栈顶元素为：" + peekTop);// 判断栈是否为空boolean isEmpty = stack.isEmpty();System.out.println("栈是否为空：" + isEmpty);// 获取栈的大小int size = stack.size();System.out.println("栈的大小为：" + size);}
}

输出结果：

弹出的栈顶元素为：30
当前栈顶元素为：20
栈是否为空：false
栈的大小为：2

除了push、pop、peek、isEmpty和size等基本操作，Stack类还提供了其他一些有用的方法，如search方法用于查询一个元素在栈中的位置，elementAt方法用于获取栈中指定位置的元素等。

需要注意的是，Stack类是线程安全的，如果需要在多线程环境中使用，可以考虑使用java.util.concurrent.ConcurrentLinkedDeque类作为线程安全的栈实现。

1.5 队列

在Java中，队列（Queue）是一种基于先进先出（FIFO）原则的数据结构。

队列可以看作是一种特殊的线性表，只允许在表的一端进行插入操作（入队），在另一端进行删除操作（出队）。

Java中提供了多种队列的实现类，常用的有java.util.LinkedList和java.util.ArrayDeque，以及java.util.concurrent.ArrayBlockingQueue和java.util.concurrent.LinkedBlockingQueue等线程安全的队列实现类。

队列的主要特点：

1. 先进先出（FIFO）原则：首先插入的元素首先被访问或删除。

2. 只允许在队尾插入元素，在队头删除元素。

下面是使用LinkedList实现队列的基本操作的示例代码：

import java.util.LinkedList;
import java.util.Queue;public class QueueExample {public static void main(String[] args) {// 创建一个队列Queue<Integer> queue = new LinkedList<>();// 入队操作queue.offer(10);queue.offer(20);queue.offer(30);// 出队操作int front = queue.poll();System.out.println("出队元素为：" + front);// 获取队头元素但不出队int peekFront = queue.peek();System.out.println("当前队头元素为：" + peekFront);// 判断队列是否为空boolean isEmpty = queue.isEmpty();System.out.println("队列是否为空：" + isEmpty);// 获取队列的大小int size = queue.size();System.out.println("队列的大小为：" + size);}
}

输出结果：

出队元素为：10
当前队头元素为：20
队列是否为空：false
队列的大小为：2

除了offer、poll、peek、isEmpty和size等基本操作，队列实现类还提供了其他一些有用的方法，如element方法用于获取队头元素但不出队，remove方法用于删除队头元素等。

需要注意的是，LinkedList是非线程安全的队列实现类，如果需要在多线程环境中使用，可以考虑使用java.util.concurrent包下的线程安全队列实现类。