項目倉庫：https://gitee.com/bossDuy/hand-tear-collection-series
基于b站up生生大佬：https://www.bilibili.com/video/BV1Kp5tzGEc5/?spm_id_from=333.788.videopod.sections&vd_source=4cda4baec795c32b16ddd661bb9ce865

LinkedList

package com.yb0os1.List;import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;public class MyLinkedList<E> implements List<E> {private int size;private Node<E> tail;//尾節點private Node<E> head;//頭節點@Override//尾插法public void add(E element) {Node<E> node = new Node<>(tail, element, null);//尾插法if (tail != null) tail.next = node;else head = node;tail = node;++size;}@Override//對應的下標插入元素public void add(E element, int index) {//先判斷index是否合法if (index < 0 || index > size) {throw new IndexOutOfBoundsException("index:" + index + "size:" + size);}//尾插if (size == index) {add(element);return;}//中間插入 先找到在那個位置插入Node<E> indexNode = findNode(index);Node<E> newNode = new Node<>(indexNode.prev, element, indexNode);if (indexNode.prev == null) {//代表indexNode是頭節點head = newNode;} else {indexNode.prev.next = newNode;}indexNode.prev = newNode;++size;}private Node<E> findNode(int index) {Node<E> cur = head;while (index-- > 0) {cur = cur.next;}return cur;}@Overridepublic E remove(int index) {//先判斷index是否合法if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("index:" + index + "size:" + size);}//找到要刪除的節點Node<E> indexNode = findNode(index);if (indexNode.prev == null) {//頭節點head = indexNode.next;} else{//非頭節點indexNode.prev.next = indexNode.next;}if (indexNode.next == null) {//尾節點tail = indexNode.prev;} else {//非尾節點indexNode.next.prev = indexNode.prev;}indexNode.next = null;indexNode.prev = null;--size;return indexNode.value;}@Overridepublic boolean remove(E element) {Node<E> curNode = head;int index = 0;while (curNode != null) {if (Objects.equals(element, curNode.value)) {remove(index);return true;}++index;curNode = curNode.next;}return false;}@Overridepublic E set(E element, int index) {//先判斷index是否合法if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("index:" + index + "size:" + size);}Node<E> indexNode = findNode(index);E oldValue = indexNode.value;indexNode.value = element;return oldValue;}@Overridepublic E get(int index) {//先判斷index是否合法if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("index:" + index + "size:" + size);}Node<E> indexNode = findNode(index);return indexNode.value;}@Overridepublic int size() {return size;}/*** Returns an iterator over elements of type {@code T}.** @return an Iterator.*/@Overridepublic Iterator<E> iterator() {return new LinkedListIterator();}private class LinkedListIterator implements Iterator<E> {Node<E> curNode = head;@Overridepublic boolean hasNext() {return curNode!=null;}/*** Returns the next element in the iteration.** @return the next element in the iteration* @throws NoSuchElementException if the iteration has no more elements*/@Overridepublic E next() {if (curNode==null){throw new NoSuchElementException();}E value = curNode.value;curNode = curNode.next;return value;}}private class Node<E> {E value;Node<E> next;//后繼Node<E> prev;//前驅public Node(E value) {this.value = value;}public Node(Node<E> prev, E value, Node<E> next) {this.value = value;this.next = next;this.prev = prev;}}
}

ArrayList

package com.yb0os1.List;import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;public class MyArrayList<E> implements List<E> {private Object[] table;//默認private final static int DEFAULT_CAPACITY = 10;//默認容量private int size;//實際的大小public MyArrayList() {this.table = new Object[DEFAULT_CAPACITY];}public MyArrayList(int initialCapacity) {if (initialCapacity < 0)throw new IllegalArgumentException("Illegal Capacity: " +initialCapacity);this.table = new Object[initialCapacity];}//插入一個元素，在size的位置插入元素 也就是尾端插入元素@Overridepublic void add(E element) {//先判斷size是否等于容量，等于的話需要先擴容，不等于才可以插入if (size >= table.length) {resize();}table[size++] = element;}//在對應的index插入元素@Overridepublic void add(E element, int index) {//先判斷index是否合法if (index < 0 || index > size) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}//判斷是否需要擴容后if (table.length == size) {resize();}//插入邏輯，也就是在0~size的位置插入元素了 需要后移System.arraycopy(table, index, table, index + 1, size - index);table[index] = element;size++;}//刪除對應下標位置的元素@Overridepublic E remove(int index) {System.out.println( "remove(int index)");//先判斷index是否合法if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}E oldElement = (E) table[index];System.arraycopy(table, index + 1, table, index, size - index - 1);table[--size] = null;return oldElement;}@Overridepublic boolean remove(Object element) {System.out.println( "remove(Object element)");for (int i = 0; i < size; i++) {if (Objects.equals(element, table[i])) {remove(i);return true;}}return false;}//修改下標為index位置的元素為element@Overridepublic E set(E element, int index) {//先判斷index是否合法if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}E oldElement = (E) table[index];table[index] = element;return oldElement;}@Overridepublic E get(int index) {//先判斷index是否合法if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}return (E) table[index];}@Overridepublic int size() {return this.size;}//數組擴容的邏輯private void resize() {//1.5倍擴容Object[] newTable = new Object[table.length + (table.length >> 1)];System.out.println("擴容了,原數組大小" + table.length + ",現在數組大小" + newTable.length);// 從內存的角度把一個數組元素的引用裝到另外一個數組上System.arraycopy(table, 0, newTable, 0, table.length);this.table = newTable;}/*** Returns an iterator over elements of type {@code T}.** @return an Iterator.*/@Overridepublic Iterator<E> iterator() {return new ArrayIterator();}private class ArrayIterator implements Iterator<E> {int cursor = 0;//判斷是否有下一個元素@Overridepublic boolean hasNext() {return cursor != size;}@Overridepublic E next() {if (!hasNext())throw new NoSuchElementException();return (E) table[cursor++];}}
}