提示信息

Java实现的数据结构与算法:顺序表

风情万种 已关注

顺序表(也称为动态数组或数组列表)是一种常用的数据结构,用于存储一定数量的元素,并支持快速的索引访问。在Java中,顺序表的实现可以通过使用数组来完成。下面是如何使用Java实现顺序表的一个简单示例:

  1. public class MyArrayList<T> {
  2. private Object[] elements;
  3. private int size;
  4. private static final int DEFAULT_CAPACITY = 10;
  5. // Constructor with default capacity
  6. public MyArrayList() {
  7. this.elements = new Object[DEFAULT_CAPACITY];
  8. this.size = 0;
  9. }
  10. // Constructor with custom capacity
  11. public MyArrayList(int initialCapacity) {
  12. if (initialCapacity < 0) {
  13. throw new IllegalArgumentException("Capacity must be non-negative");
  14. }
  15. this.elements = new Object[initialCapacity];
  16. this.size = 0;
  17. }
  18. // Adds an element to the end of the list
  19. public void add(T element) {
  20. ensureCapacity(size + 1);
  21. elements[size++] = element;
  22. }
  23. // Ensures there's enough capacity to hold new elements
  24. private void ensureCapacity(int minCapacity) {
  25. if (minCapacity > elements.length) {
  26. int newCapacity = elements.length * 2;
  27. if (newCapacity < minCapacity) {
  28. newCapacity = minCapacity;
  29. }
  30. Object[] newElements = new Object[newCapacity];
  31. System.arraycopy(elements, 0, newElements, 0, size);
  32. elements = newElements;
  33. }
  34. }
  35. // Retrieves an element at a specified index
  36. public T get(int index) {
  37. checkIndex(index);
  38. return (T) elements[index];
  39. }
  40. // Removes an element at a specified index
  41. public T remove(int index) {
  42. checkIndex(index);
  43. T oldValue = (T) elements[index];
  44. int numMoved = size - index - 1;
  45. if (numMoved > 0) {
  46. System.arraycopy(elements, index + 1, elements, index, numMoved);
  47. }
  48. elements[--size] = null; // Clear to let GC do its work
  49. return oldValue;
  50. }
  51. // Returns the number of elements in the list
  52. public int size() {
  53. return size;
  54. }
  55. // Checks if an index is within the bounds of the list
  56. private void checkIndex(int index) {
  57. if (index < 0 || index >= size) {
  58. throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
  59. }
  60. }
  61. // Example usage
  62. public static void main(String[] args) {
  63. MyArrayList<Integer> list = new MyArrayList<>();
  64. list.add(1);
  65. list.add(2);
  66. list.add(3);
  67. System.out.println("Element at index 1: " + list.get(1)); // Output: 2
  68. System.out.println("List size: " + list.size()); // Output: 3
  69. list.remove(1);
  70. System.out.println("List size after removal: " + list.size()); // Output: 2
  71. }
  72. }

说明

  1. 数据存储:使用一个数组来存储元素。
  2. 动态扩容ensureCapacity方法用于在添加新元素时,检查并增加数组容量。
  3. 添加元素add方法用于在列表末尾添加元素。
  4. 获取元素get方法通过索引获取元素。
  5. 删除元素remove方法通过索引移除元素,并调整后续元素的位置。
  6. 边界检查checkIndex用于确保索引在有效范围内。

这个简单的实现展示了顺序表的基本操作以及如何关键的动态扩容等特性的实现。Java中的ArrayList是此数据结构的一个强大实现,提供了许多优化和额外的功能。

    遇到难题? "AI大模型GPT4.0、GPT" 是你的私人解答专家! 点击按钮去提问......
风情万种 关注 已关注

最近一次登录:2024-11-20 21:10:02   

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