- Java内置了 java.util.LinkedList 类，它是 Java 标准库中的一部分，用于表示双向链表（Doubly Linked List）。
我们可以参照该类进行设计
需求分析
链表是由一个个数据节点构成，换句话说，我们将每条数据储存在链表中的每一个数据节点中。同时每个节点要负责帮助我们找到下一个节点在哪里。所以我们需要一个内置Node类，它的内部有一个数据，一个节点指针。
private class Node {
E data;
Node next;//下一个节点的地址
Node(E data) {
this.data = data;
this.next = null;
}
}
回到链表本身，我们需要记录整个链表的大小，size， 不仅如此，我也要一个头指针帮我定位整个链表的起始点。
public class MyLinkedList<E> {
private class Node {
E data;
Node next;
Node(E data) {
this.data = data;
this.next = null;
}
}
private Node head;
private int size;
public MyLinkedList() {
head = null;
size = 0;
}
}
功能实现
- 1.添加元素
这个功能很容易理解，不过呢，我们肯定不能满足仅仅append元素。应该允许我们指定位置插入
// 在链表末尾添加元素
public void add(E data) {
add(size, data);
}
/**
* 在指定位置插入一个元素。
* @param index 插入位置的索引，从0开始。
* @param data 要插入的元素。
* @throws IndexOutOfBoundsException 如果索引小于0或大于当前列表大小，则抛出异常。
*/
public void add(int index, E data) {
// 检查索引是否超出范围
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
Node newNode = new Node(data); // 创建新节点
// 当索引为0时，将新节点插入到链表头部
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++; // 更新列表大小
}
- 2.删除元素
有增加就需要有删除
/**
* 删除链表中指定位置的元素。
* @param index 要删除的元素的位置索引。
* @throws IndexOutOfBoundsException 如果索引超出链表范围，则抛出异常。
*/
public void remove(int index) {
// 检查索引是否超出链表范围
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
// 如果删除的是头节点
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--; // 更新链表大小
}
/**
* 删除链表中指定数据的元素。
* @param data 要删除的元素数据。
*/
public void remove(E data) {
// 如果链表为空，则直接返回
if (head == null) {
return;
}
// 如果头节点数据与要删除的数据相等，则将头节点指向下一个节点，并更新大小
if (head.data.equals(data)) {
head = head.next;
size--;
return;
}
// 从第二个节点开始遍历链表，寻找要删除的数据
Node current = head;
while (current.next != null) {
// 如果找到要删除的数据，则跳过该节点，并更新大小
if (current.next.data.equals(data)) {
current.next = current.next.next;
size--;
return;
}
current = current.next;
}
}
- 3.查询元素
/**
* 获取链表中指定位置的元素。
*
* @param index 要获取元素的位置，从0开始计数。
* @return 链表中指定位置的元素。
* @throws IndexOutOfBoundsException 如果指定位置超出链表范围（小于0或大于等于链表长度）。
*/
public E get(int index) {
// 检查索引是否超出链表范围
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
Node current = head;
// 遍历链表，直到达到指定位置
for (int i = 0; i < index; i++) {
current = current.next;
}
return current.data; // 返回指定位置的元素
}
- 4.其他方法
// 返回链表的大小
public int size() {
return size;
}
// 清空链表
public void clear() {
head = null; //垃圾回收器会自动清理内存
size = 0;
}
全部代码
public class MyLinkedList<E> {
private class Node {
E data;
Node next;
Node(E data) {
this.data = data;
this.next = null;
}
}
private Node head;
private int size;
public MyLinkedList() {
head = null;
size = 0;
}
// 在链表末尾添加元素
public void add(E data) {
add(size, data);
}
/**
* 在指定位置插入一个元素。
* @param index 插入位置的索引，从0开始。
* @param data 要插入的元素。
* @throws IndexOutOfBoundsException 如果索引小于0或大于当前列表大小，则抛出异常。
*/
public void add(int index, E data) {
// 检查索引是否超出范围
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
Node newNode = new Node(data); // 创建新节点
// 当索引为0时，将新节点插入到链表头部
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 int size() {
return size;
}
// 清空链表
public void clear() {
head = null;
size = 0;
}
/**
* 获取链表中指定位置的元素。
*
* @param index 要获取元素的位置，从0开始计数。
* @return 链表中指定位置的元素。
* @throws IndexOutOfBoundsException 如果指定位置超出链表范围（小于0或大于等于链表长度）。
*/
public E get(int index) {
// 检查索引是否超出链表范围
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
Node current = head;
// 遍历链表，直到达到指定位置
for (int i = 0; i < index; i++) {
current = current.next;
}
return current.data; // 返回指定位置的元素
}
/**
* 删除链表中指定位置的元素。
* @param index 要删除的元素的位置索引。
* @throws IndexOutOfBoundsException 如果索引超出链表范围，则抛出异常。
*/
public void remove(int index) {
// 检查索引是否超出链表范围
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
// 如果删除的是头节点
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--; // 更新链表大小
}
/**
* 删除链表中指定数据的元素。
* @param data 要删除的元素数据。
*/
public void remove(E data) {
// 如果链表为空，则直接返回
if (head == null) {
return;
}
// 如果头节点数据与要删除的数据相等，则将头节点指向下一个节点，并更新大小
if (head.data.equals(data)) {
head = head.next;
size--;
return;
}
// 从第二个节点开始遍历链表，寻找要删除的数据
Node current = head;
while (current.next != null) {
// 如果找到要删除的数据，则跳过该节点，并更新大小
if (current.next.data.equals(data)) {
current.next = current.next.next;
size--;
return;
}
current = current.next;
}
}
public static void main(String[] args) {
MyLinkedList<Integer> list = new MyLinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(1, 4); // 在索引1处插入元素4
System.out.println("Size of LinkedList after insertion: " + list.size());
System.out.println("Element at index 1: " + list.get(1));
}
}