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

Java实现数据结构线性表和链表

news 2026/8/23 4:52:29

1、首先定义接口

/** * 线性表接口 * @param <T> 元素类型 */ public interface LinearList<T> { /** * 添加元素到表尾 * @param element 要添加的元素 * @return 是否添加成功 */ boolean add(T element); /** * 在指定位置插入元素 * @param index 插入位置 * @param element 要插入的元素 * @return 是否插入成功 */ boolean add(int index, T element); /** * 删除指定位置的元素 * @param index 要删除的位置 * @return 被删除的元素 */ T remove(int index); /** * 删除指定元素 * @param element 要删除的元素 * @return 是否删除成功 */ boolean remove(T element); /** * 获取指定位置的元素 * @param index 位置 * @return 该位置的元素 */ T get(int index); /** * 修改指定位置的元素 * @param index 位置 * @param element 新元素 * @return 原元素 */ T set(int index, T element); /** * 查找元素的位置 * @param element 要查找的元素 * @return 元素的位置，不存在返回-1 */ int indexOf(T element); /** * 检查线性表是否包含指定元素 * @param element 要检查的元素 * @return 是否包含 */ boolean contains(T element); /** * 获取线性表的大小 * @return 元素个数 */ int size(); /** * 检查线性表是否为空 * @return 是否为空 */ boolean isEmpty(); /** * 清空线性表 */ void clear(); /** * 遍历线性表 */ void traverse(); }

2、顺序线下表实现

/** * 顺序表实现 * @param <T> 元素类型 */ public class ArrayList<T> implements LinearList<T> { private static final int DEFAULT_CAPACITY = 10; private T[] elements; private int size; @SuppressWarnings("unchecked") public ArrayList() { elements = (T[]) new Object[DEFAULT_CAPACITY]; size = 0; } @SuppressWarnings("unchecked") public ArrayList(int capacity) { if (capacity <= 0) { throw new IllegalArgumentException("容量必须大于0"); } elements = (T[]) new Object[capacity]; size = 0; } @Override public boolean add(T element) { ensureCapacity(); elements[size++] = element; return true; } @Override public boolean add(int index, T element) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("索引越界：" + index); } ensureCapacity(); // 移动元素 for (int i = size; i > index; i--) { elements[i] = elements[i - 1]; } elements[index] = element; size++; return true; } @Override public T remove(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("索引越界：" + index); } T removed = elements[index]; // 移动元素 for (int i = index; i < size - 1; i++) { elements[i] = elements[i + 1]; } elements[--size] = null; // 避免内存泄漏 return removed; } @Override public boolean remove(T element) { int index = indexOf(element); if (index != -1) { remove(index); return true; } return false; } @Override public T get(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("索引越界：" + index); } return elements[index]; } @Override public T set(int index, T element) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("索引越界：" + index); } T old = elements[index]; elements[index] = element; return old; } @Override public int indexOf(T element) { if (element == null) { for (int i = 0; i < size; i++) { if (elements[i] == null) { return i; } } } else { for (int i = 0; i < size; i++) { if (element.equals(elements[i])) { return i; } } } return -1; } @Override public boolean contains(T element) { return indexOf(element) != -1; } @Override public int size() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public void clear() { for (int i = 0; i < size; i++) { elements[i] = null; // 避免内存泄漏 } size = 0; } @Override public void traverse() { System.out.print("顺序表: ["); for (int i = 0; i < size; i++) { System.out.print(elements[i]); if (i < size - 1) { System.out.print(", "); } } System.out.println("]"); } /** * 确保容量足够 */ private void ensureCapacity() { if (size >= elements.length) { // 扩容为原来的2倍 @SuppressWarnings("unchecked") T[] newElements = (T[]) new Object[elements.length * 2]; System.arraycopy(elements, 0, newElements, 0, size); elements = newElements; } } }

3、链表实现

/** * 链表实现 * @param <T> 元素类型 */ public class LinkedList<T> implements LinearList<T> { private Node<T> head; private int size; private static class Node<T> { T data; Node<T> next; Node(T data) { this.data = data; this.next = null; } } public LinkedList() { head = null; size = 0; } @Override public boolean add(T element) { Node<T> newNode = new Node<>(element); if (head == null) { head = newNode; } else { Node<T> current = head; while (current.next != null) { current = current.next; } current.next = newNode; } size++; return true; } @Override public boolean add(int index, T element) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("索引越界：" + index); } Node<T> newNode = new Node<>(element); if (index == 0) { newNode.next = head; head = newNode; } else { Node<T> prev = getNode(index - 1); newNode.next = prev.next; prev.next = newNode; } size++; return true; } @Override public T remove(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("索引越界：" + index); } T removed; if (index == 0) { removed = head.data; head = head.next; } else { Node<T> prev = getNode(index - 1); removed = prev.next.data; prev.next = prev.next.next; } size--; return removed; } @Override public boolean remove(T element) { if (head == null) { return false; } if (head.data == null ? element == null : head.data.equals(element)) { head = head.next; size--; return true; } Node<T> prev = head; Node<T> current = head.next; while (current != null) { if (current.data == null ? element == null : current.data.equals(element)) { prev.next = current.next; size--; return true; } prev = current; current = current.next; } return false; } @Override public T get(int index) { return getNode(index).data; } @Override public T set(int index, T element) { Node<T> node = getNode(index); T old = node.data; node.data = element; return old; } @Override public int indexOf(T element) { Node<T> current = head; for (int i = 0; i < size; i++) { if (current.data == null ? element == null : current.data.equals(element)) { return i; } current = current.next; } return -1; } @Override public boolean contains(T element) { return indexOf(element) != -1; } @Override public int size() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public void clear() { head = null; size = 0; } @Override public void traverse() { System.out.print("链表: ["); Node<T> current = head; while (current != null) { System.out.print(current.data); if (current.next != null) { System.out.print(", "); } current = current.next; } System.out.println("]"); } /** * 获取指定位置的节点 * @param index 位置 * @return 节点 */ private Node<T> getNode(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("索引越界：" + index); } Node<T> current = head; for (int i = 0; i < index; i++) { current = current.next; } return current; } }

4、测试

/** * 线性表测试类 */ public class LinearListTest { public static void main(String[] args) { System.out.println("测试顺序表："); testLinearList(new ArrayList<>()); System.out.println("\n测试链表："); testLinearList(new LinkedList<>()); } private static void testLinearList(LinearList<Integer> list) { // 添加元素 list.add(1); list.add(2); list.add(3); list.traverse(); // 在指定位置插入元素 list.add(1, 5); list.traverse(); // 获取元素 System.out.println("索引2的元素：" + list.get(2)); // 修改元素 System.out.println("修改索引1的元素，原元素：" + list.set(1, 6)); list.traverse(); // 查找元素 System.out.println("元素3的位置：" + list.indexOf(3)); System.out.println("是否包含元素6：" + list.contains(6)); // 删除元素 System.out.println("删除索引1的元素：" + list.remove(1)); list.traverse(); // 删除指定元素 System.out.println("删除元素3：" + list.remove(Integer.valueOf(3))); list.traverse(); // 检查大小和是否为空 System.out.println("大小：" + list.size()); System.out.println("是否为空：" + list.isEmpty()); // 清空列表 list.clear(); System.out.println("清空后是否为空：" + list.isEmpty()); list.traverse(); } }

实现内容

  1. 线性表接口(LinearList<T>)

    • 定义了线性表的基本操作方法，如添加、插入、删除、获取、修改、查找等
    • 提供了统一的接口，使得顺序表和链表可以通过相同的方式使用

  2. 顺序表实现(ArrayList<T>)

    • 基于数组实现，支持动态扩容
    • 提供了高效的随机访问能力
    • 适用于频繁访问元素的场景

  3. 链表实现(LinkedList<T>)

    • 基于节点实现，每个节点包含数据和指向下一个节点的引用
    • 支持高效的插入和删除操作
    • 适用于频繁插入和删除元素的场景

  4. 测试类(LinearListTest)

    • 演示了如何使用顺序表和链表
    • 测试了各种操作方法的功能

如何使用

  1. 创建线性表实例：

    • 顺序表：LinearList<Integer> arrayList = new ArrayList<>();
    • 链表：LinearList<Integer> linkedList = new LinkedList<>();

  2. 调用线性表的方法：

    • 添加元素：list.add(1);
    • 插入元素：list.add(1, 5);
    • 删除元素：list.remove(1);
    • 获取元素：list.get(2);
    • 修改元素：list.set(1, 6);
    • 查找元素：list.indexOf(3);
    • 遍历元素：list.traverse();

  3. 运行测试：

    • 执行LinearListTest类的main方法，查看测试结果

代码特点

  • 泛型设计：使用泛型使得线性表可以存储任意类型的数据
  • 异常处理：对索引越界等情况进行了异常处理
  • 内存管理：在顺序表中避免了内存泄漏
  • 性能优化：顺序表支持动态扩容，链表提供了高效的插入删除操作
  • 代码结构清晰：接口与实现分离，便于维护和扩展

http://www.cnnetsun.cn/news/1436518.html

相关文章：

  • FXAS21002陀螺仪驱动开发：寄存器配置、FreeRTOS安全访问与抗干扰优化
  • Windows下Redis服务启动报错1067？5种排查方法实测（附终极解决方案）
  • mPLUG视觉问答作品展示：餐厅菜单价格识别案例
  • 工业时序数据特征提取工具箱：从统计特征到深度学习特征
  • HSTracker：macOS炉石传说玩家的智能决策辅助系统
  • LeetCode：148. 排序链表
  • EcomGPT-7B电商模型数据库课程设计参考：构建智能电商知识图谱系统
  • 玩转T型三电平并网控制：手撕C代码实现工业级控制方案
  • Phi-3-Mini-128K生产环境：金融风控规则文档动态更新与影响面自动分析
  • SerialNetworkBridge：嵌入式串口网络桥接框架
  • 汉化 Claude Code 的命令提示
  • 瀚高数据库安全避坑指南：5次输错密码就锁定？这些配置项必须改
  • 顺序表和链表
  • 【RS】从8位到64位：遥感影像位深如何影响地物识别与信息提取
  • SMOTE实战：用Python轻松搞定数据不平衡问题（附完整代码）
  • 松灵机器人二次开发实战：从零搭建Ubuntu环境到ROS包部署（避坑指南）
  • Mi-Create：零基础打造个性化小米穿戴表盘的终极指南
  • SecGPT-14B开源模型实战：中小企业低成本构建专属网络安全智能助手
  • 2026 大型企业网盘选型指南：为何说“同步性能”比“存储空间”更决定成败？
  • 高校科研数据总是丢？教育行业选企业网盘必须死磕的 3 个硬指标（含 5 款主流实测）
  • 丹青识画GPU算力调度：K8s Device Plugin管理书法渲染GPU资源
  • SILVACO TCAD实战：从网格划分到掺杂定制的SPAD器件结构构建
  • 用MATLAB手把手教你仿真3发4收毫米波雷达阵列信号（附完整代码）
  • 避免数据丢失！RK3399系统固件备份与恢复的5个关键步骤（含常见问题解答）
  • Linux驱动开发：环境准备与报错处理
  • AI写春联教程：5分钟上手春联生成模型，零基础也能创作吉祥对联
  • 从零开始：手把手教你用ROS Melodic在Ubuntu 18.04上跑通VINS-Mono（避坑指南）
  • 3分钟掌握Open Interpreter：本地代码执行AI助手的终极指南
  • Z-Image Atelier 自动化测试集成：基于软件测试理论的生成结果验证框架
  • GTE-Base-ZH助力AIGC内容审核：语义相似度匹配实战