手写ArrayList和LinkedList

项目仓库：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++];}}
}