[!quote] 物理结构

数据的逻辑结构在计算机中的存储形式

数组

[!hint] 数组的内存分配方式

读取，修改

int arr[] = new int[3];  
arr[0] = 1;  

// 读取
int i = arr[0];  
// 修改
arr[0] = 2;

中间插入

public class Array {
    private int array[];
    // 数组元素的数量
    private int size;

    // 传入数组的容量capacity来构造Array
    public Array(int capacity) {
        this.array = new int[capacity];
        size = 0;
    }

    // 数组扩容
    public void resize() {
        int newArray[] = new int[array.length * 2];
        for (int i = 0; i < size; i++) {
            newArray[i] = array[i];
        }
        array = newArray;
    }

    public void insert(int element, int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("超出数组范围");
        }

        // 如果数组满了，就扩容
        if (size == array.length) {
            resize();
        }

        // 从右向左循环，把元素逐个向右挪一位
        for (int i = size - 1; i >= index; i--) {
            array[i + 1] = array[i];
        }

        // 放入新元素
        array[index] = element;
        size++;
    }

    public static void main(String[] args) {
        Array a1 = new Array(3);
        a1.insert(8, 0);
        a1.insert(7, 1);
        System.out.println(a1.array[0] + " " + a1.array[1]);
    }
}

---
8 7

删除

public class DeleteArray {
    int array[];
    int size;

    public int Delete(int index) throws Exception {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出数组元素范围");
        }

        int deleteElement = array[index];
        //从左往右循环,将index后面的元素往前覆盖
        for (int i = index + 1; i < size; i++) {
            array[i - 1] = array[i];
        }
        size--;
        return deleteElement;
    }
}

链表

[!quote] 链表

• 链表无需考虑扩容问题

[!hint] 链表的两种形式

• 
• 

创建结点

public class MyLinkedList {
	private Node head;  //头结点指针  
	private Node last;  //尾结点指针  
	private int size;   //链表长度

	// 一个Node为一个结点
	class Node {  
	    int data;  
	    Node next; // 这个结点的第二个元素next是下一个结点
	    
		Node(int data) {  
		    this.data = data;  
		    next = null;
		}
	}
}

Java 会自动初始化，把 `head` 和 `last` 设置为 `NULL`，所以不用担心套娃

读取

public Node get(int index) throws Exception {
	if (index < 0 || index >= size) {
		throw new IndexOutOfBoundsException("超出链表结点范围");
	}
	// 从头结点开始一个一个next
	Node temp = head;
	for (int i = 0; i < index; i++) {
		temp = temp.next;
	}
	return temp;
}

插入

public void insert(int data, int index) throws Exception {  
    if (index < 0 || index > size) {  
        throw new IndexOutOfBoundsException("超出链表的结点范围");  
    }  

	// 创建一个被添加的新对象
    Node insertedNode = new Node(data);  
    // 空链表
    if (size == 0) {  
        head = insertedNode;  
        last = insertedNode;  
    } else if (index == 0) {  
	    // 头部插入
        insertedNode.next = head;  
        head = insertedNode;  
    } else if (index == size) {  
	    // 尾部插入
        last.next = insertedNode;  
        last = insertedNode;  
    } else {    // 插入到中间
	    // 读取到前一个Node
        Node preNode = get(index - 1);  
        insertedNode.next = preNode.next;  
        preNode.next = insertedNode;  
    }  
    size++;  
}

删除

public Node remove(int index) throws Exception {
	if (index < 0 || index >= size) {
		throw new IndexOutOfBoundsException("超出链表结点范围");
	}
	
	Node removeNode;
	
	if (index == 0) {   // 删除头结点
		removeNode = head;
		head = head.next;
	} else if (index == size - 1) {   // 删除尾结点
		removeNode = last;
		Node preNode = get(index - 1);
		last = preNode;
	} else {    // 删除中间结点
		Node preNode = get(index - 1);
		removeNode = preNode.next;
		preNode.next = preNode.next.next;
	}
	size--;
	return removeNode;
}

遍历

public void output() {
	Node temp = head;
	while (temp != null) {
		System.out.println(temp.data);
		temp = temp.next;
	}
}