数组和链表示意图

目的

不用java标准库
自己时间 一个 arraylist 和 linked list

区别

数组

数组 支持 随机访问 可以立即访问
根据 第一个元素的位置， 推算出 第三个地方的位置

如下图所示，假设我们知道 头的位置是X
数组是 int类型
每个位置就是 占4个字节
所以第三个元素的位置应该是 X + 3 x 4
即为 X + 12
就可以直接访问 第三个位置，直接进行赋值操作。

C语言有句话， 数组是指针， 指针不是数组。
我们 可以 把 数组就当做指针
我们知道 指针，即为 第一个元素位置
我们又可以根据 数组的类型 推断出 每个位置的大小
然后 通过 arr + X x 元素大小 直接推算出我们想修改的位置。

链表

链表存储的元素，它们不是连在一起放在内存的。
而是 分散位于 不同的位置。

通过 next指针记录下一个元素位置是多少，然后找到下一个元素。

只能通过 next指针 一个一个访问。

但是对于数组来说，每删除一个元素，需要将后面的所有元素都 往前移动1个位置。

对数组的增加操作，也类似，需要将后面的所有元素都 往后移动1个位置。

对于链表来说，增删都比较方便。

另外，对于数组来说，一开始就设置固定大小空间，当数组满了之后，需要重新申请一块新的空间，更大的
然后 将所有元素 都 移动过去。

数据结构的本质

遍历 和 访问

都是增删查改

postion 和 index的区别

数组实现

import java.util.NoSuchElementException;public class MyArrayList{// 真正存储的数据private E[] data;private int size;private static final int INIT_CAP = 1;public MyArrayList() {this(INIT_CAP);}public MyArrayList(int initCapacity) {data = (E[])new Object[initCapacity];}/** 增 **/// 在数组尾部添加一个元素 epublic void addLast(E e) {// 边界条件 Boundary conditionsif (data.length == size) {resize(data.length * 2); // 扩容 Expansion}data[size]= e;size++;}// 在index 索引位置添加一个元素 elementprivate void add(int index, E element) {checkPositionIndex(index); // 注意这里检查positionif (data.length == size) {resize(data.length * 2); // 扩容 Expansion}// data[index...] -> data[index+1 ....]// 数据迁移 Data migrationSystem.arraycopy(data, index, data, index + 1, size - 1);// 数据赋值 Data assignmentdata[index] = element;size++;}/** 删 **/// 删除数组的最后一个元素 并 返回public E removeLast() {if (isEmpty()) { // 数组为空throw new NoSuchElementException();}if (size < data.length / 4) { // 缩容 Shrinkageresize(data.length / 2);}E last = data [size - 1];// 删除最后一个元素 Delete the last elementdata[size - 1] = null;size--;return last;}// 删除index 对应的元素 并返回public E remove(int index) {checkElementIndex(index);if (size < data.length / 4) {resize (data.length / 2);}// 数据迁移// data[index + 1....] -> data[index...]E delVal = data[index];System.arraycopy(data, index + 1, data,  index,size - index - 1);// 删除最后一个元素data[size - 1] = null;size--;return delVal;}/** 查 **/// 返回索引 index 对应的元素public E get(int index) {checkElementIndex(index);return data[index];}/** 改 **/// 将索引 index的元素 修改为 element 并返回之前的值public E set(int index, E element) {checkElementIndex(index);E oldVal = data[index];data[index] = element;return oldVal;}/** 工具函数 */public int size() {return size;}public boolean isEmpty() {return size == 0;}/*** 私有函数*/// 明确index 和 postion区别private boolean isElementIndex(int index) {return index >= 0 && index < size;}private boolean isPositionIndex(int index) {return index >= 0 && index <= size;}// 检查 index 索引位置是否可以存在元素private void checkElementIndex(int index) {if (!isElementIndex(index)) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}}private void checkPositionIndex(int index) {if (!isPositionIndex(index)) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}}private void resize(int newCap) {E[] temp = (E[]) new Object[newCap];System.arraycopy(data, 0, temp, 0, size);data = temp;}
}

数组增加元素(add)的图解

再写一遍。逻辑同上面

import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;public class MyArrayList implements Iterable {// 真正存储数据的底层数组 The underlying array that really stores dataprivate E[] data;// 记录当前元素个数 Record the current number of elementsprivate int size;// 默认初始容量 Default initial capacityprivate static final int INIT_CAP = 1;public MyArrayList(){this(INIT_CAP);}public MyArrayList(int initCapability) {data = (E[])new Object[initCapability];size = 0;}/** 增**/public void addLast(E e){int cap = data.length;if (size == cap) {resize(2 * cap);}data[size] = e;size++;}public void add(int index, E e){checkPositionIndex(index);int cap = data.length;if (size == cap) {resize(2 * cap);}// move dat data[index...] -> data[index + 1..]System.arraycopy(data, index, data, index + 1, size - index);data[index] = e;size++;}public void addFirst(E e){add(0, e);}/** 删*/public E removeLast(){if (size == 0) {throw new NoSuchElementException();}int cap = data.length;if (size == cap / 4) {resize(cap / 2);}E deletedE = data[size - 1];data[size - 1] = null;size--;return deletedE;}public E remove(int index){checkElementIndex(index);int cap = data.length;if (size < cap / 4) {resize(cap / 2);}E deletedE = data[index];// move data data[index + 1....] -> data[index....]System.arraycopy(data, index + 1, data, index, size - index - 1);data[size - 1] = null;size--;return deletedE;}public E removeFirst(){return remove(0);}/** 查*/public E get(int index){checkElementIndex(index);return data[index];}/** 改*/public E set(int index, E element){checkElementIndex(index);E old = data[index];data[index] = element;return old;}/** tool method functions */public int size(){return size;}public boolean isEmpty(){return size == 0;}// 修改容量大小 Modify capacity sizepublic void resize(int newCap) {if (size > newCap) return;E[] temp = (E[])new Object[newCap];/** System.arraycopy* 四个参数:*      param1: the array to copied from*      param2: the start index in original*      param3: the array to be copied in*      param4: the total no of coponments to be copied*/System.arraycopy(data, 0, temp,0 ,size);data = temp;}// Check whether there are elements in the index positionprivate boolean isElementIndex(int index) {return index >= 0 && index < size;}// Check whether elements can be added to the index position.private boolean isPositionIndex(int index) {return index >=0 && index <= size;}private void checkElementIndex(int index) {if (!isElementIndex(index)){throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}}private void checkPositionIndex(int index) {if (!isPositionIndex(index)) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}}@Overridepublic Iterator iterator(){return new Iterator() {private  int p = 0;@Overridepublic boolean hasNext() {return p != size;}@Overridepublic E next() {return data[p++];}};}private void display() {System.out.println("size = " + size + "cap = " + data.length);System.out.println(Arrays.toString(data));}public static void main(String[] args) {// 初始容量设置为 3MyArrayList arr = new MyArrayList<>(3);// 添加 5 个元素for (int i = 1; i <= 5; i++) {arr.addLast(i);}arr.remove(3);arr.add(1, 9);arr.addFirst(100);int val = (int)arr.removeLast();for (int i = 0; i < arr.size(); i++) {System.out.println(arr.get(i));}}}

链表

图解
头部添加元素

尾部插入

删除元素

在index对应位置插入元素

如果要在1的位置插入元素，首先要找到 index为 0 和 index为1的位置，然后 进行操作。


双链表实现代码

import java.util.NoSuchElementException;public class MyLinkedList {// 双链表的节点private static class Node{E val;Node next;Node prev;Node(E val){this.val = val;}}private final Node head, tail;private int size;public MyLinkedList(){this.head = new Node<>(null);this.tail = new Node<>(null);head.next = tail;tail.prev = head;this.size = 0;}/**增*/public void addFirst(E e){Node node = new Node<>(e);Node temp = head.next;// head 和 tempnode.prev = head;node.next = temp;head.next = node;temp.prev = node;size++;}public void addLast(E e){Node node = new Node<>(e);Node temp = tail.prev;// temp headnode.next = tail;node.prev = temp;tail.prev = node;temp.next = node;size++;}public void add(int index, E e){checkPositionindex(index);Node node = new Node<>(e);Node p = getNode(index);Node temp = p.prev;node.next = p;node.prev = temp;p.prev = node;temp.next = node;size++;}/**删*/public E removeFirst(){if (isEmpty()) {throw new NoSuchElementException();}Node x = head.next;Node temp = x.next;// head -> x -> temphead.next = temp;temp.prev = head;x.next = x.prev = null;size--;return x.val;}public E removeLast(){if (isEmpty()) {throw new NoSuchElementException();}Node x = tail.prev;Node temp = x.prev;// temp <-> x <-> tailtemp.next = tail;tail.prev = temp;x.prev = x.next = null;size--;return x.val;}public E remove(int index){checkElementIndex(index);Node p = getNode(index);Node prev = p.prev;Node next = p.next;// prev <-> p ;prev.next = next;next.prev = prev;p.next = p.prev = null;size--;return p.val;}/**查*/public E getFirst(){if (isEmpty()) {throw new NoSuchElementException();}return head.next.val;}public E getLast(){if (isEmpty()) {throw new NoSuchElementException();}return tail.prev.val;}public E get(int index){checkElementIndex(index);Node p = getNode(index);return p.val;}/**改*/public E set(int index, E element){checkElementIndex(index);Node p = getNode(index);E old = p.val;p.val = element;return old;}/** other utility funcations 工具函数*/public int size(){return this.size;}public boolean isEmpty(){return 0 == size;}private boolean isElementIndex(int index) {return index >= 0 && index < size;}private boolean isPositionIndex(int index) {return index >=0 && index <= size;}// 检查index索引位置是否可以存在元素// Check whether the element can exist at the index positionprivate void checkElementIndex(int index) {if (isElementIndex(index)) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}}private void checkPositionindex(int index) {if (isPositionIndex(index)) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}}private Node getNode(int index) {checkElementIndex(index);Node p = head.next;for (int i = 0; i < index; i++) {p = p.next;}return p;}
}

单链表实现

import java.util.NoSuchElementException;public class MyLinkedList {private static class Node {E val;Node next;Node(E val) {this.val = val;}}private final Node head, tail;private int size;public MyLinkedList(){this.head = new Node(null);this.tail = new Node(null);head.next = tail;this.size = 0;}/**增*/public void addFirst(E e){Node x = new Node<>(e);Node temp = head.next;// head -> temp// x-> tempx.next = temp;// head-> x -> temphead.next = x;size++;}public void addLast(E e){Node x = new Node<>(e);Node temp;// find the node before last nodeif (size > 0) {temp = getNode(size - 1);} else {temp = head;}// x-> tailx.next = tail;// temp -> x -> tailtemp.next = x;size++;}public void add(int index, E e){checkPositionIndex(index);if (index == size) {addLast(e);return;}Node x = new Node<>(e);Node temp;if (index >= 0) {temp = getNode(index - 1);} else {temp = head;}Node p = getNode(index);// x->px.next = p;// temp -> x -> ptemp.next = x;size++;}/**删*/public E removeFirst(){if (isEmpty()){throw new NoSuchElementException();}Node x = head.next;head.next = head.next.next;x.next = null;size--;return x.val;}public E removeLast(){if (isEmpty()){throw new NoSuchElementException();}Node p = getNode(size - 1);Node temp;if (size >= 2) {temp = getNode(size - 2);} else {temp = head;}// temp -> x -> tailtemp.next = tail;p.next = null;size--;return p.val;}public E remove(int index){checkElementIndex(index);Node p = getNode(index);Node prev;if (index >= 0) {prev = getNode(index - 1);} else {prev = head;}// prev -> p -> nextNode next = p.next;prev.next = next;p.next = null;size--;return next.val;}/**查*/public E getFirst(){if (isEmpty()) {throw new NoSuchElementException();}return head.next.val;}public E getLast(){if (isEmpty()) {throw new NoSuchElementException();}return getNode(size - 1).val;}public E get(int index){checkElementIndex(index);Node p = getNode(index);return p.val;}/**改*/public E set(int index, E element){checkElementIndex(index);Node p = getNode(index);E old = p.val;p.val = element;return old;}/**其他工具函数Other tool functions*/public int size(){return this.size;}public boolean isEmpty(){return this.size == 0;}public  boolean isElementIndex(int index){return index >= 0 && index < size;}public boolean isPositionIndex(int index){return index >= 0 && index <= size;}private void checkElementIndex(int index){if (isElementIndex(index)) {throw new IndexOutOfBoundsException("index: "+ index + ", size:" + size);}}private void checkPositionIndex(int index){if (isPositionIndex(index)) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}}private Node getNode(int index){checkElementIndex(index);Node p = head.next;for (int i = 0; i < index; i++) {p = p.next;}return p;}}

Leetcode练习题

易错点 注意 add(index) 和 delete(index)的两者不同
前者检查的是position
后者检查的是index

https://leetcode.com/problems/design-linked-list

class ListNode {int val;ListNode prev, next;public ListNode(int val){this.val = val;}
}
class MyLinkedList {private final ListNode head, tail;int size;public MyLinkedList(){this.head = new ListNode(-1);this.tail = new ListNode(-1);head.next = tail;tail.prev = head;this.size = 0;}public int get(int index) {if (!checkIndex(index)) return -1;ListNode p = head.next;for (int i = 0; i < index; i++) {p = p.next;}return p.val;}public void addAtHead(int val) {ListNode x = new ListNode(val);ListNode temp = head.next;x.prev = head;x.next = temp;head.next = x;temp.prev = x;this.size++;}   public void addAtTail(int val) {ListNode x = new ListNode(val);ListNode temp = tail.prev;x.next = tail;x.prev = temp;temp.next = x;tail.prev = x;this.size++;}public void addAtIndex(int index, int val) {if (!checkPostion(index)) return;ListNode x = new ListNode(val);ListNode p = getNode(index);ListNode temp = p.prev;x.prev = temp;x.next = p;temp.next = x;p.prev = x;this.size++;}public void deleteAtIndex(int index) {if (!checkIndex(index)) return;ListNode p = getNode(index);ListNode prev = p.prev;ListNode next = p.next;prev.next = next;next.prev = prev;p.next = p.prev = null;this.size--;}private boolean checkIndex(int index) {return index >= 0 && index < size;}private boolean checkPostion(int index) {return index >= 0 && index <= size;}private ListNode getNode(int index) {ListNode p = head.next;for (int i = 0; i < index; i++) {p = p.next;}        return p;}
}

Reference

https://appktavsiei5995.pc.xiaoe-tech.com/p/t_pc/course_pc_detail/video/v_62655468e4b09dda125fa007?product_id=p_626541bbe4b0812e1790e3f8&content_app_id=&type=6