当前位置：首页 > web >正文

Java复习Day22

web 2025/7/19 1:39:54

链表复习（1）：

链表基础链表是一种物理存储非连续、非顺序的数据结构，通过指针链接实现元素的逻辑顺序。它由动态生成的结点组成，每个结点包含数据域和指针域。

常见链表类型：

单向链表：结点含数据域和指向后继的指针域
双向链表：结点含数据域、前驱指针和后继指针
循环链表：首尾相连的链表形式

优势：

动态内存管理，无需预先确定数据规模
插入操作时间复杂度O(1)
内存利用率高

劣势：

查找效率低（需顺序遍历）
额外存储指针域，空间开销较大

链表实现

public class MyLinkedList<E> {private class Node<E> {Node<E> next;E data;Node<E> previous;public Node(Node<E> next, E data, Node<E> previous) {this.next = next;this.data = data;this.previous = previous;}}private Node<E> first;private Node<E> last;private int size;// 构造方法public MyLinkedList() {}public MyLinkedList(Node<E> first, Node<E> last, int size) {this.first = first;this.last = last;this.size = size;}// 核心方法public boolean add(E e) {Node<E> l = last;Node<E> newNode = new Node<>(null, e, l);last = newNode;if (l == null) {first = newNode;} else {l.next = newNode;}size++;return true;}public void add(int index, E e) {if (index == 0) {first = new Node<>(first, e, null);} else {Node<E> prev = node(index-1);Node<E> next = prev.next;Node<E> newNode = new Node<>(next, e, prev);prev.next = newNode;}size++;}private Node<E> node(int index) {Node<E> x = first;for (int i = 0; i < index; i++) {x = x.next;}return x;}public E get(int index) {return node(index).data;}public int size() {return size;}public E getFirst() {if (first == null)throw new NoSuchElementException();return first.data;}public E getLast() {if (last == null)throw new NoSuchElementException();return last.data;}public E remove(int index) {Node<E> node = first;if (index == 0) {first = node.next;} else {Node<E> prev = node(index-1);node = prev.next;prev.next = node.next;}size--;return node.data;}
}