Java数据结构之顺序表和链表精解

简介

在计算机科学中，数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通俗地讲，数据结构就是组织和存储数据的一种方式，目的是在计算机程序中高效地访问和修改数据。

顺序表

顺序表是一种线性表结构，它是由一组地址连续的存储单元组成，元素之间的物理顺序保持与逻辑顺序一致。因此，顺序表的元素可以随机访问，访问速度快，但插入和删除元素需要移动其他元素，比较耗时。

定义

在Java中，使用数组来实现顺序表，定义如下：

public class ArrayList<E> {

    private static final int DEFAULT_CAPACITY = 10;
    private Object[] elementData;
    private int size;

    public ArrayList() {
        elementData = new Object[DEFAULT_CAPACITY];
    }

    public ArrayList(int initialCapacity) {
        elementData = new Object[initialCapacity];
    }

    public int size() {
        return size;
    }

    public E get(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        return (E) elementData[index];
    }

    public void add(E e) {
        ensureCapacity(size + 1);
        elementData[size++] = e;
    }

    private void ensureCapacity(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity < minCapacity) {
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity < minCapacity) {
                newCapacity = minCapacity;
            }
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }
}

使用示例

创建一个空的ArrayList对象：

ArrayList<String> list = new ArrayList<String>();

添加元素到ArrayList中：

list.add("Java");
list.add("数据结构");
list.add("算法");

访问ArrayList中的元素：

System.out.println(list.get(0));  // Output: Java
System.out.println(list.get(1));  // Output: 数据结构
System.out.println(list.get(2));  // Output: 算法

链表

链表是一种线性表结构，它是由若干个节点组成，每个节点包含一个数据元素和指向下一个节点的指针。因此，链表的元素不能随机访问，只能从头节点开始顺序访问，访问速度比较慢，但插入和删除元素只需要修改指针，不需要移动其他元素，比较快捷。

定义

在Java中，链表使用Node类来表示节点，定义如下：

public class Node<E> {

    private E data;
    private Node<E> next;

    public Node(E data, Node<E> next) {
        this.data = data;
        this.next = next;
    }

    public E getData() {
        return data;
    }

    public Node<E> getNext() {
        return next;
    }

    public void setNext(Node<E> next) {
        this.next = next;
    }
}

由Node类可以组成链表，定义如下：

public class LinkedList<E> {

    private Node<E> head;
    private int size;

    public LinkedList() {
        head = new Node<E>(null, null);
        size = 0;
    }

    public int size() {
        return size;
    }

    public void add(E e) {
        Node<E> newNode = new Node<E>(e, null);
        Node<E> currentNode = head;
        while (currentNode.getNext() != null) {
            currentNode = currentNode.getNext();
        }
        currentNode.setNext(newNode);
        size++;
    }

    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        int i = 0;
        Node<E> currentNode = head.getNext();
        while (i < index) {
            currentNode = currentNode.getNext();
            i++;
        }
        return currentNode.getData();
    }
}

使用示例

创建一个空的LinkedList对象：

LinkedList<String> list = new LinkedList<String>();

添加元素到LinkedList中：

list.add("Java");
list.add("数据结构");
list.add("算法");

访问LinkedList中的元素：

System.out.println(list.get(0));  // Output: Java
System.out.println(list.get(1));  // Output: 数据结构
System.out.println(list.get(2));  // Output: 算法

总结

顺序表和链表都是常用的数据结构，选择哪一种数据结构要考虑具体应用场景。如果经常需要随机访问元素，应该选择顺序表；如果经常需要插入和删除元素，应该选择链表。