提示信息

Java中顺序表的模拟实现

ヽ|已于酣梦 已关注

在Java中,顺序表通常可以用数组来实现,它是一种线性数据结构,支持顺序存取和动态大小调整。以下是一个简单的顺序表(动态数组)的基本实现:

  1. public class MyArrayList<E> {
  2. private Object[] elementData; // 存储元素的数组
  3. private int size; // 当前元素个数
  4. private static final int DEFAULT_CAPACITY = 10; // 默认初始容量
  5. // 构造方法
  6. public MyArrayList() {
  7. this.elementData = new Object[DEFAULT_CAPACITY];
  8. this.size = 0;
  9. }
  10. // 获取元素的数量
  11. public int size() {
  12. return size;
  13. }
  14. // 判断是否为空
  15. public boolean isEmpty() {
  16. return size == 0;
  17. }
  18. // 获取指定位置的元素
  19. public E get(int index) {
  20. rangeCheck(index);
  21. return (E) elementData[index];
  22. }
  23. // 添加元素到末尾
  24. public void add(E element) {
  25. ensureCapacity(size + 1);
  26. elementData[size++] = element;
  27. }
  28. // 在指定位置插入元素
  29. public void add(int index, E element) {
  30. rangeCheckForAdd(index);
  31. ensureCapacity(size + 1);
  32. System.arraycopy(elementData, index, elementData, index + 1, size - index);
  33. elementData[index] = element;
  34. size++;
  35. }
  36. // 删除指定位置的元素
  37. public E remove(int index) {
  38. rangeCheck(index);
  39. E oldValue = (E) elementData[index];
  40. int numMoved = size - index - 1;
  41. if (numMoved > 0) {
  42. System.arraycopy(elementData, index + 1, elementData, index, numMoved);
  43. }
  44. elementData[--size] = null; // 释放最后一个元素的引用
  45. return oldValue;
  46. }
  47. // 确保容量足够,当容量不足时进行扩容
  48. private void ensureCapacity(int minCapacity) {
  49. if (minCapacity > elementData.length) {
  50. int newCapacity = elementData.length * 2;
  51. if (newCapacity < minCapacity) {
  52. newCapacity = minCapacity;
  53. }
  54. elementData = java.util.Arrays.copyOf(elementData, newCapacity);
  55. }
  56. }
  57. // 索引范围检查
  58. private void rangeCheck(int index) {
  59. if (index >= size || index < 0) {
  60. throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
  61. }
  62. }
  63. // 插入时索引范围检查
  64. private void rangeCheckForAdd(int index) {
  65. if (index > size || index < 0) {
  66. throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
  67. }
  68. }
  69. }

功能描述:

  • 构造函数:初始化一个默认容量的数组。
  • size():返回当前元素个数。
  • isEmpty():检查容器是否为空。
  • get(int index):根据索引获取元素。
  • add(E element):在容器末尾添加元素。
  • add(int index, E element):在指定位置插入元素。
  • remove(int index):移除指定位置的元素并返回该元素。
  • ensureCapacity(int minCapacity):确保数组有足够的容量,必要时扩容。
  • 索引检查:方法rangeCheckrangeCheckForAdd分别用于普通访问和插入操作的索引范围检查,以防止非法操作。

这是一个基础的顺序表实现,类似于Java中的ArrayList,可以根据需要进行扩展,比如实现其他接口、增加更多操作方法等。

    遇到难题? "AI大模型GPT4.0、GPT" 是你的私人解答专家! 点击按钮去提问......
ヽ|已于酣梦 关注 已关注

最近一次登录:2024-11-21 01:00:38   

暂时还没有签名,请关注我或评论我的文章
×
免费图表工具,画流程图、架构图