Java手写LinkedList和拓展

Java手写LinkedList和拓展

思维导图

实现思路原理

• 创建一个名为Node的内部类，用于表示链表中的节点。Node类应包含以下属性：

  • data：用于存储节点的数据元素。
  • prev：用于存储指向前一个节点的引用。
  • next：用于存储指向后一个节点的引用。

• 创建一个名为LinkedList的类，用于表示链表。LinkedList类应包含以下属性：

  • head：用于存储链表的头节点的引用。
  • tail：用于存储链表的尾节点的引用。
  • size：用于存储链表中节点的数量。

• 实现add方法，用于向链表中添加新的元素。该方法的实现步骤如下：

  • 创建一个新的Node对象，将要添加的数据元素作为参数传入。
  • 如果链表为空（即head为null），则将新节点设置为头节点和尾节点。
  • 否则，将新节点的prev引用设置为当前尾节点，将当前尾节点的next引用设置为新节点，并将新节点设置为新的尾节点。
  • 增加链表的大小。

• 实现get方法，用于获取指定位置的元素。该方法的实现步骤如下：

  • 检查索引是否越界，如果越界则抛出IndexOutOfBoundsException异常。
  • 从头节点开始，遍历链表，直到找到指定位置的节点。
  • 返回该节点的数据元素。

• 实现remove方法，用于删除指定位置的元素。该方法的实现步骤如下：

  • 检查索引是否越界，如果越界则抛出IndexOutOfBoundsException异常。
  • 从头节点开始，遍历链表，直到找到指定位置的节点。
  • 如果要删除的节点有前一个节点（即当前节点的prev不为null），则将前一个节点的next引用指向当前节点的下一个节点。
  • 否则，将头节点设置为当前节点的下一个节点。
  • 如果要删除的节点有后一个节点（即当前节点的next不为null），则将后一个节点的prev引用指向当前节点的前一个节点。
  • 否则，将尾节点设置为当前节点的前一个节点。
  • 减少链表的大小。

• 实现size方法，用于获取链表的长度。该方法的实现步骤如下：

  • 直接返回链表的大小属性。

详细介绍和详细步骤

创建Node类

private class Node {private T data;private Node prev;private Node next;public Node(T data) {this.data = data;this.prev = null;this.next = null;}
}

Node类用于表示链表中的节点，包含数据元素data、指向前一个节点的引用prev和指向后一个节点的引用next。构造函数用于初始化节点的数据元素。

创建LinkedList类

public class LinkedList<T> {private Node head;private Node tail;private int size;// 构造函数public LinkedList() {this.head = null;this.tail = null;this.size = 0;}// 添加元素public void add(T element) {Node newNode = new Node(element);if (head == null) {head = newNode;tail = newNode;} else {newNode.prev = tail;tail.next = newNode;tail = newNode;}size++;}// 获取元素public T get(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("Index out of range");}Node current = head;for (int i = 0; i < index; i++) {current = current.next;}return current.data;}// 删除元素public void remove(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("Index out of range");}Node current = head;for (int i = 0; i < index; i++) {current = current.next;}if (current.prev != null) {current.prev.next = current.next;} else {head = current.next;}if (current.next != null) {current.next.prev = current.prev;} else {tail = current.prev;}size--;}// 获取链表长度public int size() {return size;}
}

LinkedList类用于表示链表，包含头节点head、尾节点tail和链表长度size属性。构造函数用于初始化链表。

add方法用于向链表中添加新的元素。首先创建一个新的Node对象，并将要添加的数据元素作为参数传入。然后根据链表是否为空，将新节点设置为头节点和尾节点，或者将新节点添加到尾节点的后面。最后增加链表的大小。

get方法用于获取指定位置的元素。首先检查索引是否越界，如果越界则抛出IndexOutOfBoundsException异常。然后从头节点开始遍历链表，直到找到指定位置的节点。最后返回该节点的数据元素。

remove方法用于删除指定位置的元素。首先检查索引是否越界，如果越界则抛出IndexOutOfBoundsException异常。然后从头节点开始遍历链表，直到找到指定位置的节点。如果要删除的节点有前一个节点，则将前一个节点的next引用指向当前节点的下一个节点；否则，将头节点设置为当前节点的下一个节点。如果要删除的节点有后一个节点，则将后一个节点的prev引用指向当前节点的前一个节点；否则，将尾节点设置为当前节点的前一个节点。最后减少链表的大小。

size方法用于获取链表的长度，直接返回链表的大小属性。

总结

通过手写LinkedList的实现，我们深入理解了链表的数据结构和原理，并且加深了对Java语言的熟悉程度。我们学习了如何创建链表、添加元素、获取元素、删除元素和获取链表长度的基本功能。通过实践，我们对链表的操作和链表节点的关系有了更深入的理解。

拓展

除了基本的添加、获取和删除功能，我们还可以对LinkedList进行一些拓展，例如：

• 实现反转链表的功能，将链表中的节点顺序颠倒。
• 实现查找链表中的环，并返回环的起始节点。
• 实现合并两个有序链表的功能，将两个有序链表合并为一个有序链表。
  具体如下：

反转链表

public void reverse() {Node current = head;Node prev = null;while (current != null) {Node next = current.next;current.next = prev;prev = current;current = next;}tail = head;head = prev;
}

reverse方法用于将链表中的节点顺序颠倒。首先定义一个当前节点current和一个前一个节点prev，并将它们都初始化为null。然后使用一个循环，遍历链表中的每个节点。在循环中，首先将当前节点的下一个节点保存到一个临时变量next中，然后将当前节点的next引用指向前一个节点prev，然后将前一个节点prev更新为当前节点current，最后将当前节点current更新为下一个节点next。循环结束后，将尾节点tail更新为原来的头节点head，将头节点head更新为反转后的链表的头节点prev。

查找链表中的环

public Node findCycle() {Node slow = head;Node fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {break;}}if (fast == null || fast.next == null) {return null;}slow = head;while (slow != fast) {slow = slow.next;fast = fast.next;}return slow;
}

findCycle方法用于查找链表中的环，并返回环的起始节点。首先定义一个慢指针slow和一个快指针fast，并将它们都初始化为头节点head。然后使用一个循环，慢指针每次移动一步，快指针每次移动两步，直到快指针追上慢指针或者快指针到达链表的末尾。如果快指针追上慢指针，则说明链表中存在环。在循环结束后，如果快指针为null或者快指针的下一个节点为null，则说明链表中不存在环，返回null。否则，将慢指针重新设置为头节点head，然后使用两个指针同时移动，每次移动一步，直到两个指针相遇。相遇的节点即为环的起始节点。

合并两个有序链表

public static LinkedList<Integer> merge(LinkedList<Integer> list1, LinkedList<Integer> list2) {LinkedList<Integer> mergedList = new LinkedList<>();Node node1 = list1.head;Node node2 = list2.head;while (node1 != null && node2 != null) {if (node1.data <= node2.data) {mergedList.add(node1.data);node1 = node1.next;} else {mergedList.add(node2.data);node2 = node2.next;}}while (node1 != null) {mergedList.add(node1.data);node1 = node1.next;}while (node2 != null) {mergedList.add(node2.data);node2 = node2.next;}return mergedList;
}

merge方法用于合并两个有序链表，并返回合并后的有序链表。首先创建一个新的空链表mergedList作为合并后的链表。然后使用两个指针node1和node2分别指向两个链表的头节点。使用一个循环，比较node1和node2指向的节点的数据元素大小，将较小的数据元素添加到mergedList中，并将对应的指针向后移动一步。循环结束后，如果链表list1还有剩余的节点，则将剩余的节点添加到mergedList中。如果链表list2还有剩余的节点，则将剩余的节点添加到mergedList中。最后返回合并后的链表mergedList。

拓展总结

通过拓展部分的代码，我们实现了链表的反转、查找环和合并有序链表等功能。这些功能都是基于链表的基本操作进行实现的，通过实践我们不仅加深了对链表的理解，而且提高了编程能力。链表作为一种常用的数据结构，对于解决一些特定的问题非常有用，因此掌握链表的基本操作和常见的拓展功能对于编程能力的提升是非常有帮助的。