链表
链表是一种链式存储
的线性表,所有元素的内存地址不一定是连续的
。
单向链表
一、单向链表的设计
1.1、不带虚拟头结点
public class LinkedList<E> {
// 链表的节点数量
private int size;
// 链表的头结点
private Node<E> first;
// 静态成员内部类:static静态的、因为是成员内部类所以可以用private修饰
private static class Node<E>{
// 节点自身存储的元素
E element;
// 保存下一个节点的地址
Node<E> next;
// 因为内部类也是一个类,所以也有构造方法
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
// 不需要预先分配容量所以不需要写构造函数
}
1.2、带虚拟头结点
public class LinkedList<E> {
// 链表的节点数量
private int size;
// 链表的头结点
private Node<E> first;
// 静态内部类
private class Node<E>{
// 节点自身存储的元素
E element;
// 保存下一个节点的地址
Node<E> next;
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
// 带虚拟头节点的单链表
public LinkedList<E>() {
first = new Node<E>(null, null);
}
}
二、链表的接口设计(学习其设计思想)
- 左图:由于链表的大部分接口和动态数组一致,我们抽取出一个共同的List接口
- 右图:由于链表和动态数组中有些方法的实现完全一样,我们将这些完全相同的方法放到一个抽象类中。这样ArrayList类和LinkedList类中实现完全一样的方法就在抽象类AbstractList中(
抽象的父类,达到代码复用的目的
),而其他方法则声明在List接口中
// 动态数组和链表中都有且实现也完全一样的方法,我们抽取到AbstractList中
1、private void rangeCheck(int index)
2、private void rangeCheckForAdd(int index)
3、public int size()
4、public boolean isEmpty()
5、public boolean contains(E element)
6、public void add(E element)
2.1、List接口
package DataStructure._02链表;
public interface List<E> {
/**
* 接口是抽象方法(public abstract)和常量值(public static final)定义的集合。
*/
// 常量值
int ELEMENT_NOT_FOUND = -1;
// 清除所有元素
void clear();
// 获取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);
}
2.2、AbstractList类
package DataStructure._02链表;
/**
* @author keyongkang
* @date 2022-07-11-8:37
*/
public abstract class AbstractList<E> implements List<E> {
// 元素的数量。
// 声明为protected是为了给子类使用
protected int size;
protected void rangeCheck(int index) {
// 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
}
}
protected void rangeCheckForAdd(int index) {
// 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
}
}
// 返回元素的数量
public int size() {
return size;
}
// 判断是否为空
public boolean isEmpty() {
return size == 0;
}
// 判断是否包含某个元素
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
// 添加元素到末尾
public void add(E element) {
add(size, element);
}
}
2.3、LinkedList类
package DataStructure._02链表;
/**
* @author keyongkang
* @date 2022-07-10-19:27
*/
public class LinkedList<E> extends AbstractList<E> implements List {
// 链表的头结点
private Node<E> first;
// 静态内部类
private class Node<E>{
// 节点自身存储的元素
E element;
// 保存下一个节点的地址
Node<E> next;
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
@Override
public void clear() {
}
@Override
public E get(int index) {
return null;
}
@Override
public E set(int index, E element) {
return null;
}
@Override
public void add(int index, E element) {
}
@Override
public E remove(int index) {
return null;
}
@Override
public int indexOf(E element) {
return 0;
}
}
2.4、ArrayList类
package DataStructure._01动态数组;
import DataStructure._02链表.AbstractList;
/**
* @author keyongkang
* @date 2022-07-10-10:09
*/
public class ArrayList<E> extends AbstractList<E> implements List {
// 动态数组的所有元素
private E[] elements;
// 动态数组的默认初始容量
private static final int DEFAULT_CAPACITY = 10;
public ArrayList(int capacity) {
capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
elements = (E[])new Object[capacity];
}
public ArrayList() {
//elements = new int[DEFAULT_CAPACITY];
this(DEFAULT_CAPACITY);
}
// 添加元素到动态数组index索引位置
public void add(int index, E element) {
// // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
// if (index < 0 || index > size) {
// throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
// }
rangeCheckForAdd(index);
// 当前动态数组的元素个数为size,我们确保需要size+1个容量
ensureCapacity(size + 1);
for (int i = size - 1; i >= index; i --) {
elements[i + 1] = elements[i];
}
elements[index] = element;
size ++;
}
// 确保有needCapacity的容量
private void ensureCapacity(int needCapacity) {
// 当前容量为nowCapacity
int nowCapacity = elements.length;
// 当前容量大于等于所需要的容量,容量够
if (nowCapacity >= needCapacity) return;
// 容量不够,则扩容至1.5倍
int newCapacity = nowCapacity + (nowCapacity >> 1);
E[] newElements = (E[])new Object[newCapacity];
// 拷贝元素
for(int i = 0; i < elements.length; i ++) {
newElements[i] = elements[i];
}
elements = newElements;
System.out.println(nowCapacity + "扩容为:" + newCapacity);
}
// 返回index索引位置对应的元素
public E get(int index) {
// // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
// if (index < 0 || index >= size) {
// throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
// }
rangeCheck(index);
return elements[index];
}
// 删除index索引位置对应的元素,并返回所删除的元素
public E remove(int index) {
// // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
// if (index < 0 || index >= size) {
// throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
// }
rangeCheck(index);
// 保存要被删除的值
E remove = elements[index];
// 从被删除的后一个元素开始往前移动
for (int i = index + 1; i < size; i ++) {
elements[i - 1] = elements[i];
}
// (内存管理细节)将最后一个元素变为null
elements[size - 1] = null;
size --;
return remove;
}
// 设置index位置的元素,并返回旧值
public E set(int index, E element) {
// // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
// if (index < 0 || index >= size) {
// throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
// }
rangeCheck(index);
// 保存当前索引的旧值
E old = elements[index];
// 设置index位置的新值
elements[index] = element;
return old;
}
// 查看指定元素第一次出现的位置,如果找不到则返回-1
public int indexOf(E element) {
// 遍历动态数组。注意size和elements.length的区别
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 (element.equals(elements[i])) {
return i;
}
}
}
return ELEMENT_NOT_FOUND;
}
// 清除所有元素
public void clear() {
//size = 0;
// (内存管理细节)对象内存清空,但是对象数组所分配的内存还在
for (int i = 0; i < size; i ++) {
elements[i] = null;
}
size = 0;
}
// 打印数组
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("size = ").append(size).append(", ").append("[");
for (int i = 0; i < size; i ++) {
if (i == size - 1) {
sb.append(elements[i]);
break;
}
sb.append(elements[i]).append(", ");
}
sb.append("]");
return sb.toString();
}
}
三、(不带虚拟头节点)单链表的常用操作
3.1、清空操作clear()
@Override
public void clear() {
size = 0;
first = null;
}
- 当first指向null的时候,后面的Node将会被Java自动回收
3.2、添加操作add(int index, E element)—不带虚拟头节点
编写一个node方法用于获得index位置的节点
// node方法用于获取index位置的节点
private Node<E> node(int index) {
rangeCheck(index);
Node<E> cur = first;
for (int i = 0; i < index; i ++) {
cur = cur.next;
}
return cur;
}
@Override
public void add(int index, E element) {
// 判断index是否合法
rangeCheckForAdd(index);
if (index == 0) {
Node<E> newNode = new Node<>(element, first);
first = newNode;
} else {
Node<E> preNode = node(index - 1);
Node<E> newNode = new Node<>(element, preNode.next);
preNode.next = newNode;
}
size ++;
}
在编写链表相关操作代码过程中,要注意边界测试,比如index = 0,size - 1,size时。先写出一般情况,然后再考虑边界问题。
3.3、删除元素remove(int index)—不带虚拟头节点
@Override
public E remove(int index) {
rangeCheck(index);
E delEle;
if (index == 0) {
delEle = first.element;
first = first.next;
} else {
Node<E> preNode = node(index - 1);
delEle = preNode.next.element;
preNode.next = preNode.next.next;
}
size --;
return delEle;
}
四、(不带虚拟头节点)单链表的相关代码
package DataStructure._02链表;
/**
* @author keyongkang
* @date 2022-07-10-19:27
*/
public class LinkedList<E> extends AbstractList<E> {
// 链表的头结点
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;
}
}
@Override
public void clear() {
size = 0;
first = null;
}
@Override
public E get(int index) {
return node(index).element;
}
@Override
public E set(int index, E element) {
return null;
}
@Override
public void add(int index, E element) {
// 判断index是否合法
rangeCheckForAdd(index);
if (index == 0) {
Node<E> newNode = new Node<>(element, first);
first = newNode;
} else {
Node<E> preNode = node(index - 1);
Node<E> newNode = new Node<>(element, preNode.next);
preNode.next = newNode;
}
size ++;
}
@Override
public E remove(int index) {
rangeCheck(index);
E delEle;
if (index == 0) {
delEle = first.element;
first = first.next;
} else {
Node<E> preNode = node(index - 1);
delEle = preNode.next.element;
preNode.next = preNode.next.next;
}
size --;
return delEle;
}
@Override
public int indexOf(E element) {
if (element == null) {
Node<E> cur = first;
for (int i = 0; i < size; i ++) {
if (cur.element == null) return i;
cur = cur.next;
}
} else {
Node<E> cur = first;
for (int i = 0; i < size; i ++) {
if (element.equals(cur.element)) return i;
cur = cur.next;
}
}
return ELEMENT_NOT_FOUND;
}
// node方法用于获取index位置的节点
private Node<E> node(int index) {
rangeCheck(index);
Node<E> cur = first;
for (int i = 0; i < index; i ++) {
cur = cur.next;
}
return cur;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("size = ").append(size).append(", ").append("[");
Node<E> cur = first;
for (int i = 0; i < size; i ++) {
if (i == size - 1) {
sb.append(cur.element);
break;
}
sb.append(cur.element).append(", ");
cur = cur.next;
}
sb.append("]");
return sb.toString();
}
}
五、(带虚拟头结点)单链表的相关代码
为了统一头节点和非头节点的删除、添加处理逻辑
,可以在最前面增加一个虚拟头节点(不存储数据)
LeeCode707. 设计链表
六、ArrayList和LinkedList的时间复杂度
- size是数据规模n
注意:链表、添加删除那一刻的时间复杂度是O(1),整体操作平均下来是O(n)
双向链表
Java官方的
LinkedList
底层实现就是双向链表
一、双向链表的设计
public class DoubleLinkedList<E> extends AbstractList<E> {
private int size;
private Node<E> first;
private Node<E> last;
private static class Node<E> {
private Node<E> prev;
private E element;
private Node<E> next;
public Node(E element, Node<E> prev, Node<E> next) {
this.element = element;
this.prev = prev;
this.next = next;
}
}
}
二、双向链表的常用操作
2.1、添加操作add(int index, E element)(重点)
@Override
public void add(int index, E element) {
if (index == size) {
if (size == 0) {
first = new Node<>(null, element, null);
last = first;
} else {
Node<E> prev = node(size - 1);
Node<E> newNode = new Node<>(prev, element, null);
prev.next = newNode;
last = newNode;
}
size ++;
} else {
Node<E> next = node(index);
Node<E> prev = next.prev;
Node<E> newNode = new Node<>(prev, element, next);
next.prev = newNode;
if (prev == null) {
first = newNode;
} else {
prev.next = newNode;
}
size ++;
}
}
2.2、删除操作remove(int index)(重点)
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> node = node(index);
Node<E> prev = node.prev;
Node<E> next = node.next;
if (prev == null) { // index ==0
first = next;
} else {
prev.next = next;
}
if (next == null) { // index == size - 1
last = prev;
} else {
next.prev = prev;
}
size --;
return node.element;
}
思路:先写一般情况,然后再考虑左右边界优化代码
2.3、获取操作get(int index)
@Override
public int indexOf(E element) {
Node<E> cur = null;
if (element == null) {
cur = first;
for (int i = 0; i < size; i ++) {
if (cur.element == element) return i;
cur = cur.next;
}
} else {
cur = first;
for (int i = 0; i < size; i ++) {
if (element.equals(cur.element)) return i;
cur = cur.next;
}
}
return ELEMENT_NOT_FOUND;
}
思路:先写一般情况,然后再考虑左右边界优化代码
Node node = new Node(index);// 当前节点
Node pre = node.prev;// 前一节点
Node next = node.next;// 后一节点
三、双向链表的相关代码
package DataStructure._02链表;
/**
* @author keyongkang
* @date 2022-07-12-23:04
*/
public class DoubleLinkedList<E> extends AbstractList<E> {
private Node<E> first;
private Node<E> last;
private static class Node<E> {
private Node<E> prev;
private E element;
private Node<E> next;
public Node(Node<E> prev, E element, Node<E> next) {
this.prev = prev;
this.element = element;
this.next = next;
}
}
@Override
public void clear() {
size = 0;
first = null;
last = null;
}
@Override
public E get(int index) {
rangeCheck(index);
Node<E> cur = null;
if (index < (size >> 1)) {
cur = first;
for (int i = 0; i < index; i ++) {
cur = cur.next;
}
} else {
cur = last;
for (int i = size - 1; i > index; i --) {
cur = cur.prev;
}
}
return cur.element;
}
@Override
public E set(int index, E element) {
rangeCheck(index);
return node(index).element;
}
@Override
public void add(int index, E element) {
if (index == size) {
if (size == 0) {
first = new Node<>(null, element, null);
last = first;
} else {
Node<E> prev = node(size - 1);
Node<E> newNode = new Node<>(prev, element, null);
prev.next = newNode;
last = newNode;
}
size ++;
} else {
Node<E> next = node(index);
Node<E> prev = next.prev;
Node<E> newNode = new Node<>(prev, element, next);
next.prev = newNode;
if (prev == null) {
first = newNode;
} else {
prev.next = newNode;
}
size ++;
}
}
@Override
public E remove(int index) {
rangeCheck(index);
if (index == size - 1) {
Node<E> delNode = node(size - 1);
last = delNode.prev;
delNode.prev.next = null;
} else {
Node<E> delNode = node(index);
if (index == 0) {
first = delNode.next;
delNode.next.prev = null;
} else {
delNode.prev.next = delNode.next;
delNode.next.prev = delNode.prev;
}
}
size --;
return null;
}
@Override
public int indexOf(E element) {
Node<E> cur = null;
if (element == null) {
cur = first;
for (int i = 0; i < size; i ++) {
if (cur.element == element) return i;
cur = cur.next;
}
} else {
cur = first;
for (int i = 0; i < size; i ++) {
if (element.equals(cur.element)) return i;
cur = cur.next;
}
}
return ELEMENT_NOT_FOUND;
}
/**
* 获取index位置对应的节点对象
* @param index
* @return
*/
private Node<E> node(int index) {
rangeCheck(index);
if (index < (size >> 1)) {
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
} else {
Node<E> node = last;
for (int i = size - 1; i > index; i--) {
node = node.prev;
}
return node;
}
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("size = ").append(size).append(", ").append("[");
Node<E> cur = first;
for (int i = 0; i < size; i ++) {
if (i == size - 1) {
sb.append(cur.element);
break;
}
sb.append(cur.element).append(", ");
cur = cur.next;
}
sb.append("]");
return sb.toString();
}
}