- 动态数组存在明显的缺点：
- 首先动态扩容可能会造成内存空间的大量浪费；
- 使用链表这种数据结构就可以办到，使用多少内存，就申请多少内存，不会造成内存空间的浪费；下面引出链表这种数据结构；
链表
- 是一种链式存储的线性表，所有元素的内存地址不一定是连续的；
- 其结构如下图所示：
Snip20210330_73.png
- size与first是链表的两个属性，size是链表存储元素的个数；first是链表的首节点；
- Node是节点模型，每一个节点内部有element与next两个属性，element是数据元素，next当前节点的下一个节点(后继节点)；
链表的接口设计
- 链表的接口与动态数组的接口大致相同；
- 链表在初始化的时候不需要指定容量大小；
- 结合Java的
继承(extends)，接口(interface)，抽象(abstract)三大技术对动态数组类YYArrayList与链表类LinkedList进行重新设计： - 首先定义一个接口类
interface List<E>，内部定义声明YYArrayList与YYSingleLinkedList共用的方法；注意接口只做方法的定义声明，不会去实现方法，方法的实现交给YYArrayList与YYSingleLinkedList； - 由于YYArrayList与LinkedList有公共的方法实现，所以定义一个基类
AbstrctList<E>，将公共的方法实现封装在基类中，且让基类去实现接口List<E>，但只实现YYArrayList与YYSingleLinkedList公共的方法，这样会报错，为了让基类AbstrctList<E>只实现部分接口List<E>方法(公共部分)，且不报错，引出抽象类的技术，使用abstract关键字修饰基类AbstrctList<E>即可； - 代码实现如下所示：
【第一部分】：接口类interface List<E>
package com.example.linkedlist.list;
public interface List<E> {
/**
* 目标元素不存在,返回的默认下标index
*/
static final int ELEMENT_NOT_FOUND = -1;
/**
* 返回数组元素的数量
*/
int size();
/**
* 往数组添加目标元素
* @param element 目标元素
*/
void addObject(E element);
/**
* 在指定index位置插入元素
* @param index
* @param element
*/
void insertObjectAtIndex(int index,E element);
/**
* 删除指定index位置的元素,且返回被删除的元素
* @param index
* @return
*/
E removeObjectAtIndex(int index);
/**
* 清除所有元素
*/
void clear();
/**
* 设置指定index位置的元素,且返回原来的元素
* @param index 指定下标
* @param element 新元素
* @return 原来的元素
*/
E setObjectAtIndex(int index,E element);
/**
* 获取指定index下标的元素
* @param index 指定下标
* @return 目标元素
*/
E objectAtIndex(int index);
/**
* 查询元素的index下标
* @param element
* @return
*/
int indexOfObject(E element);
/**
* 判断数组是否为空
*/
boolean isEmpty();
/**
* 判断是否包含某个元素
* @param element 目标元素
* @return
*/
boolean containsObject(E element);
}
【第二部分】：基类AbstrctList<E>
package com.example.linkedlist.list;
public abstract class AbstrctList<E> implements List<E>{
/**
* 元素的数量
*/
protected int size;
/**
* 返回数组元素的数量
*/
public int size(){
return size;
}
/**
* 往数组添加目标元素
* @param element 目标元素
*/
public void addObject(E element){
insertObjectAtIndex(size,element);
}
/**
* 判断数组是否为空
*/
public boolean isEmpty(){
return size == 0;
}
/**
* 判断是否包含某个元素
* @param element 目标元素
* @return
*/
public boolean containsObject(E element){
//判断目标元素的index是否存在
return indexOfObject(element) != ELEMENT_NOT_FOUND;
}
/**
* index检测
* @param index
*/
public void rangeCheck(int index){
if (index < 0 || index >= size){
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
}
/**
* 针对Insert -- index检测
* @param index
*/
public void rangeCheckForInsert(int index){
if (index < 0 || index > size){
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
}
}
【第三部分】：动态数组类YYArrayList<E>
package com.example.linkedlist.list;
/**
* 动态数组
* @param <E>
*/
public class YYArrayList<E> extends AbstrctList<E>{
/**
* 存储所有元素
*/
private E[] elements;
/**
* 存储元素的默认长度
*/
private static final int DEFAULT_CAPACITY = 2;
public YYArrayList(){
//构造函数之间的调用 用到this关键字
this(DEFAULT_CAPACITY);
}
/**
* 自定义构造方法
* @param capaticy 存储元素的长度
*/
public YYArrayList(int capaticy){
capaticy = capaticy < DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capaticy;
//申请内存空间
elements = (E[])new Object[capaticy];
}
@Override
public void insertObjectAtIndex(int index, E element) {
if (element == null) return;
rangeCheckForInsert(index);
//检测是否需要进行扩容
ensureCapacity(size + 1);
for (int i = size - 1;i >= index;i--){
elements[i+1] = elements[I];
}
elements[index] = element;
size++;
}
@Override
public E removeObjectAtIndex(int index) {
rangeCheck(index);
E old = elements[index];
for (int i = index + 1;i <= size - 1;i++){
elements[i-1] = elements[I];
}
elements[--size] = null;
return old;
}
@Override
public void clear() {
//将数组中对象地址全部清空 -- 对象回收
//数组没有回收,可循环使用
for (int i = 0; i < size;i++){
elements[i] = null;
}
size = 0;
}
@Override
public E setObjectAtIndex(int index, E element) {
rangeCheck(index);
E old = elements[index];
elements[index] = element;
return old;
}
@Override
public E objectAtIndex(int index) {
rangeCheck(index);
return elements[index];
}
@Override
public int indexOfObject(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;
}
@Override
public String toString() {
StringBuffer string = new StringBuffer();
string.append("size=").append(size).append(", [");
for (int i = 0;i < size;i++){
string.append(elements[I]);
if (i != size - 1){
string.append(", ");
}
}
string.append("]");
return string.toString();
}
/**
* 保证要有capacity的容量
* @param 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);
}
}
【第四部分】：链表类YYSingleLinkedList<E>
package com.example.linkedlist.list;
/**
* 链表
* @param <E>
*/
public class YYSingleLinkedList<E> extends AbstrctList<E> {
/**
* 首节点
*/
private Node<E> first;
/**
* 内部类 -- 节点
* @param <E>
*/
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 insertObjectAtIndex(int index, E element) {
rangeCheckForInsert(index);
if (index == 0){
first = new Node<>(element,first);
}else {
Node<E> preNode = nodeOfIndex(index - 1);
preNode.next = new Node<>(element,preNode.next);
}
size++;
}
@Override
public E removeObjectAtIndex(int index) {
rangeCheck(index);
Node<E> node = first;
if (index == 0){
first = first.next;
}else {
Node<E> preNode = nodeOfIndex(index - 1);
node = preNode.next;
preNode.next = node.next;
}
size--;
return node.element;
}
@Override
public void clear() {
size = 0;
first = null;
}
@Override
public E setObjectAtIndex(int index, E element) {
Node<E> node = nodeOfIndex(index);
E old = node.element;
node.element = element;
return old;
}
@Override
public E objectAtIndex(int index) {
return nodeOfIndex(index).element;
}
@Override
public int indexOfObject(E element) {
if (element == null){
Node<E> node = first;
for (int i = 0;i < size;i++){
node = node.next;
if (node.element == null) return I;
}
}else {
Node<E> node = first;
for (int i = 0;i < size;i++){
node = node.next;
if (node.element.equals(element)) return I;
}
}
return ELEMENT_NOT_FOUND;
}
/**
* 根据index索引 返回节点
* @param index
* @return
*/
private Node<E> nodeOfIndex(int index){
rangeCheck(index);
//从首节点开始遍历
Node node = first;
for (int i= 0;i < index;i++){
node = node.next;
}
return node;
}
@Override
public String toString() {
StringBuffer string = new StringBuffer();
string.append("size=").append(size).append(", [");
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (i != 0){
string.append(", ");
}
string.append(node.element);
node = node.next;
}
string.append("]");
return string.toString();
}
-
private static class Node<E>是在YYLinkedList<E>链表类内部定义的，属于链表类的内部类，用关键字static进行修饰； -
public void insertObjectAtIndex(int index, E element)：往链表指定index位置插入元素element；
@Override
public void insertObjectAtIndex(int index, E element) {
if (index == 0){
first = new Node<>(element,first);
}else {
Node<E> preNode = nodeOfIndex(index - 1);
preNode.next = new Node<>(element,preNode.next);
}
size++;
}
- 以Snip20210330_73.png为例，在index = 2的位置插入一个新的节点(节点内部有新元素)，其实现原理如下图所示：
Snip20210330_78.png
- 首先根据当前index获取，前面一个节点preNode；
- 然后创建一个新的节点(待插入的)，让preNode的next改为指向新的节点；
- 新的节点的next指向当前的节点即preNode.next；
- 最后链表的长度size+1；
-
public E removeObjectAtIndex(int index)：移除指定index位置的元素；
@Override
public E removeObjectAtIndex(int index) {
Node<E> node = first;
if (index == 0){
first = first.next;
}else {
Node<E> preNode = nodeOfIndex(index - 1);
node = preNode.next;
preNode.next = node.next;
}
size--;
return node.element;
}
移除index=2的位置的元素，其实现原理如下图所示：
Snip20210401_79.png
- 首先根据当前index，获取前面一个节点preNode；
- 然后将preNode的next指向当前节点的下一个节点，当前节点由于没有被外界指向(引用)会自动销毁；
- 最后链表的长度size-1；
-
public void clear()：清空链表，其实现原理如下图所示：
Snip20210401_81.png
- 将链表的属性first置为null，那么链表的节点会由于没有外界的指向引用会依次回收；
- 最后链表的长度size置为0；
-
public E setObjectAtIndex(int index, E element)：设置指定index位置的元素；
@Override
public E setObjectAtIndex(int index, E element) {
Node<E> node = nodeOfIndex(index);
E old = node.element;
node.element = element;
return old;
}
- 根据index获取到当前节点node，然后直接修改其element；
- 后面几个方法的实现，逻辑简单就不做过多详述了；
链表练习案例：
【第一个案例：】删除链表中的节点
https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/
Snip20210401_82.png
- 代码实现如下：
package com.example.linkedlist.链表;
public class _18_删除链表节点 {
public void deleteListNode(ListNode node){
node.value = node.next.value;
node.next = node.next.next;
}
}
- 实现原理图如下：删除index=2的节点；
Snip20210401_84.png
- index=2的节点不删除，将后面一个节点的值直接赋值给index=2的节点；且将index=2的节点的next指向后面一个节点(index= 3)的下一个节点；
- index = 3的节点由于没有引用，会被回收；
【第二个案例：】反转一个链表
https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
Snip20210401_85.png
- 利用递归的方式实现，代码如下所示：
public class _24_反转链表 {
/**
* 返回的是反转之后的首节点
* @param head
* @return
*/
public ListNode reveserseList(ListNode head){
if (head == null || head.next == null) return head;
ListNode newHead = reveserseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
实现原理图：
Snip20210401_87.png
- 利用迭代的方式实现代码如下：
public ListNode reveserseList2(ListNode head){
ListNode newHead = null;
while (head!=null){
ListNode tempNode = head.next;
head.next = newHead;
newHead = head;
head = tempNode;
}
return newHead;
}
- 实现原理图如下：
Snip20210401_89.png
【第三个案例：】环形链表
https://leetcode-cn.com/problems/linked-list-cycle/
Snip20210401_90.png
- 代码实现如下：
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null){
if (slow == fast) return true;
slow = slow.next;
fast = fast.next.next;
}
return false;
}
- 实现原理如下图所示：
Snip20210401_91.png
- 定义两个指针，一个慢指针slow初始指向首节点，一个快指针fast初始指向第二个节点；然后进入循环体，slow每次移动一个节点单位，fast每次移动两个节点单位，在循环过程中，如果存在slow=fast，那么表明此链表有环，否则没有环；
- 快慢指针；
虚拟头节点
- 有时候为了让代码更加精简，统一所有节点的处理逻辑，可以在最前面增加一个虚拟的头节点(不存储数据)，结构如下图所示：
Snip20210401_93.png
- YYLinkedList类代码改造如下：
public class YYLinkedList2<E> extends AbstrctList<E>{
/**
* 首节点
*/
private Node<E> first;
public YYLinkedList2() {
first = new Node<>(null,null);
}
/**
* 内部类 -- 节点
* @param <E>
*/
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 insertObjectAtIndex(int index, E element) {
rangeCheckForInsert(index);
Node<E> preNode = index == 0 ? first : nodeOfIndex(index - 1);
preNode.next = new Node<>(element,preNode.next);
size++;
}
@Override
public E removeObjectAtIndex(int index) {
rangeCheck(index);
Node<E> preNode = index == 0 ? first : nodeOfIndex(index - 1);
Node<E> node = preNode.next;
preNode.next = node.next;
size--;
return node.element;
}
@Override
public void clear() {
size = 0;
first = null;
}
@Override
public E setObjectAtIndex(int index, E element) {
Node<E> node = nodeOfIndex(index);
E old = node.element;
node.element = element;
return old;
}
@Override
public E objectAtIndex(int index) {
return nodeOfIndex(index).element;
}
@Override
public int indexOfObject(E element) {
if (element == null){
Node<E> node = first;
for (int i = 0;i < size;i++){
node = node.next;
if (node.element == null) return I;
}
}else {
Node<E> node = first;
for (int i = 0;i < size;i++){
node = node.next;
if (node.element.equals(element)) return I;
}
}
return ELEMENT_NOT_FOUND;
}
/**
* 根据index索引 返回节点
* @param index
* @return
*/
private Node<E> nodeOfIndex(int index){
rangeCheck(index);
//从首节点开始遍历
Node node = first.next;
for (int i= 0;i < index;i++){
node = node.next;
}
return node;
}
@Override
public String toString() {
StringBuffer string = new StringBuffer();
string.append("size=").append(size).append(", [");
Node<E> node = first.next;
for (int i = 0; i < size; i++) {
if (i != 0){
string.append(", ");
}
string.append(node.element);
node = node.next;
}
string.append("]");
return string.toString();
}
}
- 构造方法中新增虚拟头节点的初始化；
-
private Node<E> nodeOfIndex(int index)：获取index位置的节点，应该从虚拟头节点的下一个节点开始； -
public void insertObjectAtIndex(int index, E element)：针对index = 0 做逻辑修改； -
public E removeObjectAtIndex(int index)：针对index = 0 做逻辑修改； -
public String toString()：遍历元素从虚拟头节点的下一个节点开始。 - 针对链表对虚拟头节点的改造，不一定非要采用这种方案，保持原来的链表结构，一般来说没什么大的问题。
复杂度分析
-
public E objectAtIndex(int index)：获取指定index位置的元素，内部会遍历链表找到目标元素； - 数据规模为size，即链表的元素个数；
- 最坏情况复杂度：当index = size，一直遍历到链表尾部，其复杂度为：O(n)
- 最好情况复杂度：当index = 0，其复杂度为：O(1)
- 平均复杂度：其复杂度为：O(n)
-
public E setObjectAtIndex(int index, E element)：设置指定index位置的元素，内部会遍历链表； - 最坏情况复杂度：当index = size，一直遍历到链表尾部，其复杂度为：O(n)
- 最好情况复杂度：当index = 0，其复杂度为：O(1)
- 平均复杂度：其复杂度为：O(n)
-
public void insertObjectAtIndex(int index, E element)：往指定index位置插入元素，内部会遍历链表； - 最坏情况复杂度：当index = size，一直遍历到链表尾部，其复杂度为：O(n)
- 最好情况复杂度：当index = 0，其复杂度为：O(1)
- 平均复杂度：其复杂度为：O(n)
-
public E removeObjectAtIndex(int index)：删除指定index位置的元素，内部会遍历链表； - 最坏情况复杂度：当index = size，一直遍历到链表尾部，其复杂度为：O(n)
- 最好情况复杂度：当index = 0，其复杂度为：O(1)
- 平均复杂度：其复杂度为：O(n)
单向循环链表
- 单向链表尾节点的next指针指向首节点的链表属于单向循环链表；
- 结构如下所示：
Snip20210402_115.png
- 代码实现如下：
/**
* 单向循环链表
* @param <E>
*/
public class YYSingleCircleLinkedList<E> extends AbstrctList<E> {
/**
* 首节点
*/
private Node<E> first;
/**
* 内部类 -- 节点
* @param <E>
*/
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 String toString() {
StringBuffer sb = new StringBuffer();
sb.append(element).append("_").append(next.element);
return sb.toString();
}
}
@Override
public void insertObjectAtIndex(int index, E element) {
rangeCheckForInsert(index);
if (index == 0){
Node<E> newNode = new Node<>(element,first);
//获取尾节点
Node<E> last = size == 0 ? newNode : nodeOfIndex(size - 1);
last.next = newNode;
first = newNode;
}else {
Node<E> preNode = nodeOfIndex(index - 1);
preNode.next = new Node<>(element,preNode.next);
}
size++;
}
@Override
public E removeObjectAtIndex(int index) {
rangeCheck(index);
Node<E> node = first;
if (index == 0){
if (size == 1){
first = null;
}else {
Node<E> last = nodeOfIndex(size-1);
first = first.next;
last.next = first;
}
}else {
Node<E> preNode = nodeOfIndex(index - 1);
node = preNode.next;
preNode.next = node.next;
}
size--;
return node.element;
}
@Override
public void clear() {
size = 0;
first = null;
}
@Override
public E setObjectAtIndex(int index, E element) {
Node<E> node = nodeOfIndex(index);
E old = node.element;
node.element = element;
return old;
}
@Override
public E objectAtIndex(int index) {
return nodeOfIndex(index).element;
}
@Override
public int indexOfObject(E element) {if (element == null){
Node<E> node = first;
for (int i = 0;i < size;i++){
node = node.next;
if (node.element == null) return I;
}
}else {
Node<E> node = first;
for (int i = 0;i < size;i++){
node = node.next;
if (node.element.equals(element)) return I;
}
}
return ELEMENT_NOT_FOUND;
}
/**
* 根据index索引 返回节点
* @param index
* @return
*/
private Node<E> nodeOfIndex(int index){
rangeCheck(index);
//从首节点开始遍历
Node node = first;
for (int i= 0;i < index;i++){
node = node.next;
}
return node;
}
@Override
public String toString() {
StringBuffer string = new StringBuffer();
string.append("size=").append(size).append(", [");
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (i != 0){
string.append(", ");
}
string.append(node);
node = node.next;
}
string.append("]");
return string.toString();
}
}
-
public void insertObjectAtIndex(int index, E element)：往链表指定index位置插入元素element；
@Override
public void insertObjectAtIndex(int index, E element) {
rangeCheckForInsert(index);
if (index == 0){
Node<E> newNode = new Node<>(element,first);
//获取尾节点
Node<E> last = size == 0 ? newNode : nodeOfIndex(size - 1);
last.next = newNode;
first = newNode;
}else {
if (index == size - 1){
Node<E> node = nodeOfIndex(index);
Node<E> newNode = new Node<>(element,first);
node.next = newNode;
}else {
Node<E> preNode = nodeOfIndex(index - 1);
preNode.next = new Node<>(element,preNode.next);
}
}
size++;
}
- 1> 往空链表中添加元素，原理如下图所示：
Snip20210402_121.png
- 2> 往链表的首节点添加元素，原理如下图所示：
Snip20210402_120.png
- 3> 往链表的尾节点添加元素，原理如下图所示：
Snip20210402_118.png
- 4> 往链表中间节点index=2添加元素，原理如下图所示：
Snip20210402_119.png
-
public E removeObjectAtIndex(int index)：移除指定index位置的元素
public E removeObjectAtIndex(int index) {
rangeCheck(index);
Node<E> node = first;
if (index == 0){
if (size == 1){
first = null;
}else {
Node<E> last = nodeOfIndex(size-1);
first = first.next;
last.next = first;
}
}else {
Node<E> preNode = nodeOfIndex(index - 1);
node = preNode.next;
if (index == size - 1){
preNode.next = first;
}else {
preNode.next = node.next;
}
}
size--;
return node.element;
}
- 1> 当链表只有一个节点元素时删除节点，原理如下图所示：
Snip20210402_127.png
- 2> 当删除链表的首节点，原理如下图所示：
Snip20210402_126.png
- 3> 当删除链表的中间节点index=1，原理如下图所示：
Snip20210402_124.png
- 4> 当删除链表的尾节点，原理如下图所示：
Snip20210402_125.png
