数据结构——链表

目录

一、链表

1、单向链表

单向链表的遍历方式：

2、循环链表

3、双向链表

二、自行车停放（双向链表）

---

 

一、链表

•  链表是由许多相同数据类型的数据项按特定顺序排列而成的线性表
• 特性：存放的位置是不连续且随机的，动态分配内存
  • 内存泄漏（Memory Leak）：变量使用了内存存放，使用后，没有释放内存
• 优点：插入或删除数据方便
• 缺点：查找不方便，要按序查找数据
• Java中常见的链表实现类：
  • LinkedList 
    • 基于链表实现，插入和删除操作时间复杂度为 O(1)，因为只需修改节点的指针。
    • 不支持随机访问，需要从头部或尾部开始遍历链表以访问特定位置的元素，时间复杂度为 O(n)。
    • 可存储相同的元素
    • 增删元素后，链表里的元素下标不会发生变化
    • 适用于插入删除操作频繁、读取操作相对较少的场景。另外，LinkedList还可以作为队列或栈来使用。

  • ArrayList 

    • 基于数组实现，支持随机访问，根据索引可以在 O(1) 的时间复杂度内访问元素。
    • 插入和删除操作需要移动元素，时间复杂度为 O(n)。如果在末尾插入或删除元素，时间复杂度为 O(1)。
    • 增删元素后，会自动调整链表里元素的下标
    • 适用于读取操作频繁、插入删除操作相对较少的场景。
  • ListNode 则是自定义节点类，通常用于手动实现链表结构。

1、单向链表

• 单向链表是一种数据结构，其中的每个节点包含数据和一个指向下一个节点的引用。
• 链表的第一个节点称为头节点，最后一个节点的引用指向 null。这意味着在单向链表中，只能从头节点开始，按顺序遍历到最后一个节点，而无法逆向遍历。

单向链表的示例代码：

// 定义链表节点，包含节点数据和指向下一个节点的引用
class Node {int data;Node next;// 节点构造函数public Node(int data) {this.data = data;this.next = null;}
}// 定义链表
class LinkedList {Node head;// 链表构造函数public LinkedList() {this.head = null;}// 在链表末尾添加节点public void append(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;}}// 删除特定数值节点public void delete(int data) {if (head == null) {return;}if (head.data == data) {head = head.next;return;}Node current = head;while (current.next != null) {if (current.next.data == data) {current.next = current.next.next;return;}current = current.next;}}// 打印链表public void printList() {Node current = head;while (current != null) {System.out.print(current.data + " ");current = current.next;}System.out.println();}
}

单向链表的遍历方式：

在 Java 中，可以使用不同的方法来遍历 List。以下是几种常用的遍历方法：

1. 使用 for 循环：

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");for (int i = 0; i < list.size(); i++) {String element = list.get(i);System.out.println(element);
}

2. 使用增强型 for 循环（foreach 循环）：

for (String element : list) {System.out.println(element);
}

3. 使用迭代器（Iterator）：

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {String element = iterator.next();System.out.println(element);
}

2、循环链表

• 循环链表和普通链表的区别在于循环链表的末尾节点指向链表的头部节点，形成一个环形结构。这种特殊的连接方式使得循环链表可以无限地往后遍历下去，直到再次经过链表的起始节点。

• 循环链表可以是单向的，也可以是双向的，它们在实际应用中通常用于模拟循环队列或者循环缓冲区等结构。

• 在循环链表中，基本的节点结构和普通链表一样，每个节点包含一个数据域和一个指向下一个节点的指针。

• 循环链表通常具有一些特殊的操作，比如判断链表是否为空、遍历链表的方法等，这些操作和普通链表有所不同。在实际编程中，设计和操作循环链表需要特别注意避免陷入无限循环的情况。

循环链表的示例代码：

// 定义循环链表节点类
class ListNode {int val;ListNode next;// 节点类的构造函数ListNode(int val) {this.val = val;this.next = null;}
}// 定义循环链表类
class CircularLinkedList {private ListNode tail;  // 循环链表的尾节点// 添加节点到循环链表尾部public void addToTail(int value) {ListNode newNode = new ListNode(value);if (tail == null) {tail = newNode;tail.next = tail;  // 只有一个节点时，让节点指向自己形成循环} else {newNode.next = tail.next;  // 新节点指向头节点tail.next = newNode;       // 原尾节点指向新节点tail = newNode;            // 更新尾节点为新节点}}// 从循环链表中删除指定数值的节点public void deleteNode(int value) {if (tail != null) {ListNode current = tail;while (current.next != tail) {if (current.next.val == value) {current.next = current.next.next;  // 绕过匹配节点return;}current = current.next;}// 当只有一个节点时需要特殊处理if (tail.val == value) {if (tail == tail.next) {tail = null;  // 移除最后一个节点} else {tail.next = tail.next.next;  // 只有一个节点时删除自身}}}}// 遍历循环链表并打印节点数值public void printList() {if (tail != null) {ListNode current = tail.next;  // 头节点do {System.out.print(current.val + " ");current = current.next;} while (current != tail.next);}System.out.println();}
}

3、双向链表

• 双向链表是一种数据结构，它由多个节点组成。
• 每个节点包含两个指针，一个指向前一个节点，另一个指向后一个节点。这使得在双向链表中，每个节点都可以直接访问其前一个节点和后一个节点。
• 双向链表相对于单向链表的优势在于可以双向遍历链表，可以在 O(1) 时间复杂度内实现在任意位置插入和删除节点。

双向链表的示例代码：

//双向链表节点的定义，每个节点包含一个整数值和两个指针，分别指向前一个节点和后一个节点。
class ListNode {int val;ListNode prev;ListNode next;// 构造函数ListNode(int val) {this.val = val;this.prev = null;this.next = null;}
}class DoublyLinkedList {ListNode head;// 在链表头部插入节点void insertAtHead(int val) {ListNode newHead = new ListNode(val);if (head != null) {newHead.next = head;head.prev = newHead;}head = newHead;}// 在链表尾部插入节点void insertAtTail(int val) {ListNode newTail = new ListNode(val);if (head == null) {head = newTail;return;}ListNode current = head;while (current.next != null) {current = current.next;}current.next = newTail;newTail.prev = current;}// 删除指定数值的节点void deleteNode(int val) {ListNode current = head;while (current != null) {if (current.val == val) {if (current.prev != null) {current.prev.next = current.next;} else {head = current.next;}if (current.next != null) {current.next.prev = current.prev;}return;}current = current.next;}}
}

二、自行车停放（双向链表）

分析：

•  如果用单向链表，当n较大时，运行会超时

package no1_1;
import java.util.*;public class Main {public static class TreeNode {int left;int right;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 读取输入的值 n 和 kint n = sc.nextInt();TreeNode[] node = new TreeNode[100000 + 2];int k = sc.nextInt();// 初始化节点数组for (int i = 0; i <= 100001; i++) {node[i] = new TreeNode();node[i].left = -1;node[i].right = -1;}// 构建链表结构node[k].left = 0;node[k].right = 100001;node[0].right = k;node[n + 1].left = k;// 读取边的信息，构建链表for (int i = 0; i < n - 1; i++) {int x = sc.nextInt();int y = sc.nextInt();int z = sc.nextInt();if (z == 0) {// 在 y 的左边插入节点 xnode[x].left = node[y].left;node[x].right = y;node[node[y].left].right = x;node[y].left = x;} else {// 在 y 的右边插入节点 xnode[x].right = node[y].right;node[x].left = y;node[node[y].right].left = x;node[y].right = x;}}// 遍历链表并输出结果int index = 0;for (;;) {if (node[index].right == 100001) break;System.out.print(node[index].right + " ");index = node[index].right;}}
}