数据结构与算法学习笔记02-单向链表

1 结构：List-》AbstractList-》ArrayList，LinkedList

package 链表;public interface List<E> {//默认公共static final int ELEMENT_NOT_FOUND = -1;/*** 清除所有元素*/void clear();/*** 元素的数量*/int size();/*** 是否为空*/boolean isEmpty();/*** 是否包含某个元素*/boolean contains(E element);/*** 添加元素到尾部* @param element*/void add(E element);/*** 获取index位置的元素*/E get(int index);/*** 设置index位置的元素*/E set(int index, E element);/*** 在index位置插入一个元素*/void add(int index, E element);/*** 删除index位置的元素*/E remove(int index);/*** 查看元素的索引*/int indexOf(E element);}

package 链表;public abstract class AbstractList<E> implements List<E>{/*** 元素的数量*/protected int size;/*** 元素的数量 */public int size() {return size;}/*** 是否为空*/public boolean isEmpty() {return size == 0;}//封装报错protected void outOfBounds(int index) {throw new IndexOutOfBoundsException("Index"+index+",Size:"+size);}protected void rangeCheck(int index) {if(index<0||index>=size) {outOfBounds(index);}}protected void rangeCheckForAdd(int index) {if(index<0||index>size) {outOfBounds(index);}}/*** 是否包含某个元素*/public boolean contains(E element) {return indexOf(element)!=ELEMENT_NOT_FOUND;}/*** 添加元素到尾部*/public void add(E element) {add(size,element);}}

package 链表;public class LinkedList<E> extends AbstractList<E>{// 因为继承自AbstractList，所以不需要：private int size;否则会报越界异常//头结点private Node<E> first;private static class Node<E> {E element;Node<E> next;public Node(E element,Node<E> next) {this.element = element;this.next = next;}}public void clear() {size = 0;first = null;}public int size() {return size;}public boolean isEmpty() {return size == 0;}public boolean contains(E element) {return indexOf(element)!=ELEMENT_NOT_FOUND;}public E get(int index) {return node(index).element;}public E set(int index, E element) {Node<E> node = node(index);E oldE = node.element;node.element = element;return oldE;}public void add(int index, E element) {if(index == 0) {System.out.println("已进入");first = new Node<>(element, first);}else {Node<E> preNode = node(index-1);//将结点2插入结点1和结点3中间：先让结点2指向结点3，然后让结点1指向结点2!!!preNode.next = new Node<>(element, preNode.next);}size++;}public E remove(int index) {rangeCheck(index);Node<E> node = first;if (index == 0) {first = first.next;}else {Node<E> preNode = node(index-1);node = preNode.next;preNode.next = node.next;}size--;return node.element;}public int indexOf(E element) {if(element==null) {Node<E> node = first;for (int i = 0; i < size; i++) {if (node.element == null) {return i;}node = node.next;}}else {Node<E> node = first;for(int i=0;i<size;i++) {if(element.equals(node.element)) return i;node = node.next;}}return ELEMENT_NOT_FOUND;}/*** @Description:获取index位置对应结点对象*/private Node<E> node(int index) {rangeCheck(index);Node<E> node = first;for (int i = 0; i < index; i++) {node = node.next;}return node;}public String toString() {StringBuilder stringBuilder = new StringBuilder();stringBuilder.append("size=").append(size).append(",[");Node<E> node = first;for (int i = 0; i < size; i++) {if(i!=0) {stringBuilder.append(",");}stringBuilder.append(node.element);node = node.next;}stringBuilder.append("]");//Node<E> node1 = first;//while(node1!=null) {//node1 = node1.next;//}return stringBuilder.toString();}}

package 链表;//消除警告@SuppressWarnings("unchecked")public class ArrayList<E> extends AbstractList<E>{/*** 所有的元素*/private E[] elements;private static final int DEFAULT_CAPACITY = 10;//初始化数组public ArrayList(int capaticy) {capaticy = (capaticy<DEFAULT_CAPACITY)?DEFAULT_CAPACITY:capaticy;//因为所有类都继承自object，所以先new Object数组，再强转elements = (E[])new Object[capaticy];}//无参数则默认大小为10public ArrayList() {//调用有参的构造函数!!!this(DEFAULT_CAPACITY);}/*** 清除所有元素*/public void clear() {for (int i = 0; i < size; i++) {elements[i] = null;}//不能用：elements = null; 因为会断掉数组（栈）指向堆的空间，堆内部东西会销毁，每次都需要重新开辟空间。size = 0;}/*** 获取index位置的元素*/public E get(int index) {rangeCheck(index);return elements[index];}/*** 设置index位置的元素* @return 历史的元素*/public E set(int index,E element) {rangeCheck(index);E old = elements[index];elements[index] = element;return old;}/*** 在index位置插入一个元素*/public void add(int index,E element) {rangeCheckForAdd(index);ensureCapacity(size+1);for (int i = size-1; i >= index; i--) {elements[i+1] = elements[i];}elements[index] = element;size++;}/*** 删除index位置的元素*/public E remove(int index) {rangeCheck(index);E old = elements[index];for (int i = index+1; i < size; i++) {elements[i-1] = elements[i];}elements[--size]=null;return old;}/*** 查看元素的位置*/public int indexOf(E element) {if(element==null) {for (int i = 0; i < size; i++) {if (elements[i] == null) {return i;}}}else {for(int i=0;i<size;i++) {if(elements[i].equals(element)) return i;}}return ELEMENT_NOT_FOUND;}/*** 数组转换成字符串*/@Overridepublic String toString() {StringBuilder stringBuilder = new StringBuilder();stringBuilder.append("size=").append(size).append(",[");for (int i = 0; i < size; i++) {if(i!=0) {stringBuilder.append(",");}stringBuilder.append(elements[i]);//if(i!=size-1) {//stringBuilder.append(",");//}}stringBuilder.append("]");return stringBuilder.toString();}/*** @Description:保证容量至少有capacity*/private void ensureCapacity(int capacity) {int oldCapacity = elements.length;if(oldCapacity>=capacity) return;//新容量为旧容量的1.5倍int newCapacity = oldCapacity+(oldCapacity>>1);E[] newElements = (E[])new Object[newCapacity];//将原数组的元素填入新数组for (int i = 0; i < size; i++) {newElements[i] = elements[i];}//原数组指向新数组elements = newElements;System.out.println("扩容："+oldCapacity+"至"+newCapacity);}}

2 虚拟头结点：减少头结点与其他结点操作差异

package 链表;/*** 增加虚拟头结点*/public class LinkedList2<E> extends AbstractList<E>{private Node<E> first;//虚拟头结点public LinkedList2() {first = new Node<>(null, null);}...public void add(int index, E element) {rangeCheckForAdd(index);Node<E> preNode = index == 0?first:node(index-1);preNode.next = new Node<>(element, preNode.next);size++;}public E remove(int index) {rangeCheck(index);Node<E> preNode = index == 0?first:node(index-1);Node<E> node = preNode.next;preNode.next = node.next;size--;return node.element;}...}