小型企业门户网站制作,成都到西安机票,宁夏做网站好的公司,如何网站seojava线性表 三、线性表1.1 顺序表1.2 链表1.2.1 单向链表#xff08;Singly Linked List#xff09;1.2.2 双向链表#xff08;Doubly Linked List#xff09; 1.3 LinkedList VS ArrayList1.3.7 使用 LinkedList 的场景 1.4 栈1.5 队列 三、线性表
线性表是一种经典的数据… java线性表 三、线性表1.1 顺序表1.2 链表1.2.1 单向链表Singly Linked List1.2.2 双向链表Doubly Linked List 1.3 LinkedList VS ArrayList1.3.7 使用 LinkedList 的场景 1.4 栈1.5 队列 三、线性表
线性表是一种经典的数据结构它遵循线性逻辑结构的特点。
在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 类来创建一个顺序表。例如
ArrayListString 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 缓存算法。少量元素和迭代遍历 相比 ArrayListLinkedList 在内存占用上通常更高所以当列表中的元素数量较少时使用 LinkedList 可能更加合适。此外LinkedList 可以通过迭代器进行遍历适用于需要随机访问的场景。
1.3.7.2 注意事项
在使用 LinkedList 时需要注意以下几点 非线程安全 LinkedList 不是线程安全的如果需要在多线程环境中使用需要进行适当的同步或使用线程安全的列表实现如 Vector 或 CopyOnWriteArrayList。 内存占用 由于需要为每个节点额外存储前后节点的引用LinkedList 在相同数量元素的情况下可能会占用更多的内存。因此当需要存储大量元素时需要注意内存消耗的问题。 遍历和随机访问操作 相对于 ArrayListLinkedList 的遍历和随机访问效率较低。如果需要快速地随机访问元素或遍历整个列表请考虑使用其他的列表实现方式。 性能问题 在实际的应用中LinkedList 需要在空间和时间上权衡性能。在某些情况下LinkedList 的性能可能不如其他的列表实现方式。因此在选择使用 LinkedList 时需要结合具体的应用场景和性能需求做出选择。 总而言之LinkedList 适用于频繁的插入和删除操作、实现队列或栈的功能、用作缓存或缓冲区等场景。当元素数量较少且需要迭代遍历时也可以考虑使用 LinkedList。需要注意的是LinkedList 是非线程安全的如果在多线程环境中使用链表需要进行适当的同步。综上所述Java中提供了内置的 LinkedList 类来实现链表。
链表适用于频繁的插入和删除操作但访问特定位置的元素效率较低。
使用链表时需要注意其线程安全性并根据需要选择单向链表或双向链表的实现方式。
1.4 栈
在Java中栈Stack是一种基于后进先出LIFO原则的数据结构。
它可以看作是一种特殊的线性表只允许在表的一端进行插入和删除操作这一端被称为栈顶。Java中提供了栈的标准实现类即java.util.Stack类。除了Stack类还可以使用ArrayDeque类来实现栈的功能。
栈的主要特点 后进先出LIFO的原则最后插入的元素首先被访问或删除。 只允许在栈顶进行操作栈的插入操作通常被称为推入push删除操作通常被称为弹出pop。
下面是使用Stack类实现栈的基本操作的示例代码
import java.util.Stack;public class StackExample {public static void main(String[] args) {// 创建一个空栈StackInteger 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等线程安全的队列实现类。
队列的主要特点 先进先出FIFO原则首先插入的元素首先被访问或删除。 只允许在队尾插入元素在队头删除元素。
下面是使用LinkedList实现队列的基本操作的示例代码
import java.util.LinkedList;
import java.util.Queue;public class QueueExample {public static void main(String[] args) {// 创建一个队列QueueInteger 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包下的线程安全队列实现类。
