Java数据结构

Java数据结构学习记录

前言
本文仅用于个人对于数据结构的理解与学习，可能存在诸多不足之处，并且顺序为主播个人的随意的学习顺序，会有诸多杂乱之处。

目录

• 线性表
  -概念
  -特征
  -实现方式
  -线性表基本操作
  -顺序表和链表的对比

---

线性表

一. 概念

线性表是一种逻辑结构，描述的是数据元素之间的一对一的线性关系。它是一个抽象概念，不涉及具体存储方式。

二. 特征

1. 有限性： 由有限个元素组成。
2. 有序性： 元素有先后顺序（不是数值大小顺序，而是逻辑位置顺序）。
3. 唯一性： 每个元素有唯一的前驱和后继（首元素无前驱，尾元素无后继）。
4. 同类型： 通常由相同类型的元素组成。

三.实现方式

1. 顺序存储（顺序表）
使用数组实现，元素在内存中连续存储

// 顺序表的Java实现示例
class SequenceList<T> {
    private Object[] elements;  // 存储元素的数组
    private int size;           // 当前元素个数
    private int capacity;       // 容量
    
    // 初始化
    public SequenceList(int capacity) {
        this.capacity = capacity;
        this.elements = new Object[capacity];
        this.size = 0;
    }
    
    // 获取元素
    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        return (T) elements[index];  // O(1)时间复杂度
    }
    
    // 插入元素
    public void insert(int index, T element) {
        if (size == capacity) {
            resize();  // 扩容
        }
        // 将index后的元素后移
        for (int i = size; i > index; i--) {
            elements[i] = elements[i-1];  // O(n)时间复杂度
        }
        elements[index] = element;
        size++;
    }
}

2. 链式存储（链表）
元素在内存中离散存储，通过指针链接。

// 链表的Java实现示例
class LinkedList {
    class Node {
        T data;
        Node next;
        
        Node(T data) {
            this.data = data;
        }
    }
    
    private Node head;  // 头节点
    private int size;
    
    // 插入元素
    public void insert(int index, T data) {
        Node newNode = new Node<>(data);
        if (index == 0) {
            newNode.next = head;
            head = newNode;
        } else {
            Node prev = getNode(index - 1);  // 找到前驱节点
            newNode.next = prev.next;
            prev.next = newNode;
        }
        size++;
    }
    
    // 获取元素需要遍历
    public T get(int index) {
        return getNode(index).data;  // O(n)时间复杂度
    }
}

四.线性表基本操作

线性表通常支持以下基本操作（ADT抽象数据类型）：

public interface LinearList {
    // 1. 初始化
    void init();
    
    // 2. 获取长度
    int length();
    
    // 3. 判断是否为空
    boolean isEmpty();
    
    // 4. 获取元素
    T get(int index);
    
    // 5. 查找元素位置
    int locate(T element);
    
    // 6. 插入元素
    void insert(int index, T element);
    
    // 7. 删除元素
    T delete(int index);
    
    // 8. 清空列表
    void clear();
    
    // 9. 遍历操作
    void traverse();
}

五.顺序表和链表的对比

操作	顺序表	单链表	双向链表
访问元素	O(1)	O(n)	O(n)
插入/删除（已知位置）/头部插入	O(n)	O(1)	O(1)
尾部插入	O(1)（无扩容）	O(n)	O(1)(有尾指针)
空间分配	预先分配/动态扩容	动态分配	动态分配
内存使用	无额外开销	每个节点都有指针开销	每个节点都有两个指针开销
缓存友好性	好	差	差

---