目录
01 简介
- 简介是如下所示:
- 链表的设计方案是如下所示:
- ?链表的设计代码是如下所示:
public class LinkedList { private int size; private Node firstNode;//由于是只是在链表之中进行使用,因此我们设计成内部类 private static class Node<E>//这里的节点内部类要进行设计成为相应的私有静态的,不要问为什么. { E element;//内部类是一般不写访问的权限的 Node<E> next; //构造函数 public Node(E element, Node<E> next) { this.element = element; this.next = next; } } }
02 接口设计
- 链表的接口大部分和动态数组是一致的.因此,创建一个父类List,只是数组和链表的实现方式是不一样的.
? ????????但是这里二者数组和链表内容是完全不一样的,使用父类的方式并不是最佳的方式进行,可以使用接口进行创建.
- ?ArrayList和LinkedList还是存在一定的公共的相同的东西,因此,这里还是可以使用公共的线型表进行表示.
- ?经过上述处理之后List接口的代码是:
/* */ public interface List<E> { static final int ELEMENT_NOT_FOUND = -1; void clear(); int size(); boolean isEmpty(); boolean contains(E var1); void add(E var1); E get(int var1); E set(int var1, E var2); void add(int var1, E var2); E remove(int var1); int indexOf(E var1); }AbstractList之中的代码是:
public abstract class AbstractList<E> implements List<E>{//这里是只是实现一些公共的方法,因此,这里是使用abstract方式,对于外界是不可见的. protected int size; public int size() { return size; } /** * 是否为空 * @return */ public boolean isEmpty() { return size == 0; } /** * 是否包含某个元素 * @param element * @return */ public boolean contains(E element) { return indexOf(element) != ELEMENT_NOT_FOUND; } /** * 添加元素到尾部 * @param element */ public void add(E element) { if(element == null) return; add(size, element); } 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); } } }ArrayList之中的代码是:
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; elements = (E[]) new Object[capaticy]; } public ArrayList() { this(DEFAULT_CAPACITY); } /** * 清除所有元素 */ public void clear() { /* 这样的含义就是数组之中都是null,但是数组内存是存在的,不能够进行销毁, 不能够使用element=null,相当于第一根线断了,不能够继续使用. 能循环利用的留下,不能够循环利用的滚蛋. */ for (int i = 0; i < size; i++) { elements[i] = null; } size = 0; } /** * 获取index位置的元素 * @param index * @return */ public E get(int index) { rangeCheck(index); return elements[index]; } /** * 设置index位置的元素 * @param index * @param element * @return 原来的元素? */ public E set(int index, E element) { rangeCheck(index); E old = elements[index]; elements[index] = element; return old; } /** * 在index位置插入一个元素 * @param index * @param element */ public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacity(size + 1); for (int i = size; i > index; i--) { elements[i] = elements[i - 1]; } elements[index] = element; size++; } /** * 删除index位置的元素 * @param index * @return */ 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 void remove(E element) { remove(indexOf(element)); } /** * 查看元素的索引 * @param element * @return */ public int indexOf(E element) { if (element == null) { // 1 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; // n } } return ELEMENT_NOT_FOUND; } // public int indexOf2(E element) { // for (int i = 0; i < size; i++) { // if (valEquals(element, elements[i])) return i; // 2n // } // return ELEMENT_NOT_FOUND; // } // // private boolean valEquals(Object v1, Object v2) { // return v1 == null ? v2 == null : v1.equals(v2); // } /** * 保证要有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); } @Override public String toString() { // size=3, [99, 88, 77] StringBuilder string = new StringBuilder(); string.append("size=").append(size).append(", ["); for (int i = 0; i < size; i++) { if (i != 0) { string.append(", "); } string.append(elements[i]); // if (i != size - 1) { // string.append(", "); // } } string.append("]"); return string.toString(); } }LinkedList之中的代码是:
public class LinkedList<E> extends AbstractList<E>{ int ELEMENT_NOT_FOUND = -1; private int size; private Node firstNode;//由于是只是在链表之中进行使用,因此我们设计成内部类 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() { } 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); } public E get(int var1) { return null; } public E set(int var1, E var2) { return null; } public void add(int var1, E var2) { } public E remove(int var1) { return null; } public int indexOf(E var1) { return 0; } }
03 clear
- 清空元素
- ?代码块如下所示:
public void clear() {
size = 0;
first = null;
}
04 add
- 添加元素的结构示意图:
- ?通过index获取相应的节点的方式是如下所示:
/*
获取index对应位置的节点对象
*/
private Node<E> node(int index)//这里的含义就是传入一个索引,返回当下的节点
{
//检查索引是否存在
rangeCheck(index);
//比如,想要找到索引为2的位置,需要索引进行next两次
Node<E> node = first;
for (int i = 0;i < index;i++)
{
node = node.next;
}
return node;
}
由上所示,可以得知set和get方法的使用:
public E get(int index) {
return node(index).element;
}
public E set(int index, E element) {
Node<E> node = node(index);
E old = node.element;
node.element = element;
return old;
}- 添加元素的代码是如下所示:
public void add(int index, E element) { //如果要是传入的index是0 if(index == 0)//添加到最前面的位置 { first = new Node<>(element,first); } else { Node<E> prev = node(index-1); prev.next = new Node<E>(element,prev.next); //这是 } size++; }
?注意:临界和边界位置处理
05 remove
- 删除元素
public E remove(int index) {
//被删除的节点
Node<E> node = first;
if(index == 0)
{
first = first.next;
}
else
{
Node<E> prev = node(index-1);
node = prev.next;
prev.next = prev.next.next;
}
size--;
return node.element;
}06 indexOf_toString
private Node<E> node(int index)//这里的含义就是传入一个索引,返回当下的节点
{
//检查索引是否存在
rangeCheck(index);
//比如,想要找到索引为2的位置,需要索引进行next两次
Node<E> node = first;
for (int i = 0;i < index;i++)
{
node = node.next;
}
return node;
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
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();
}07 删除节点
- 一个神奇的网站https://visualgo.net/zh
- 刷个题: ??????237. 删除链表中的节点 - 力扣（LeetCode）
https://leetcode.cn/problems/delete-node-in-a-linked-list/
这里的方式是进行覆盖的过程,使用下一个的值去指向前一个节点的值,指针的改变和以往是一样的.
08 反转链表( 递归)
刷题:
-
-
代码段如下所示:
package 链表; public class _206_反转链表 { /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public class ListNode { int val; ListNode next; ListNode() { } ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } public ListNode reverseList(ListNode head) { if(head == null) return null; if(head.next == null) return head; ListNode newHead = reverseList(head.next); head.next.next = head;//4的next指向5 head.next = null;//5的next指向null return newHead; } } }
09 反转链表(迭代)
- 代码思路:
重复上述操作,将上面的东西进行串联. - ?代码块是如下所示:
public ListNode reverseList2(ListNode head) { if(head == null) return null; if(head.next == null) return head; ListNode newHead = null; while(head != null) { ListNode tmp = head.next; head.next = newHead; newHead = head; head = tmp; } return newHead; }
10 反转链表(环形链表)
- 刷题141. 环形链表 - 力扣（LeetCode）https://leetcode.cn/problems/linked-list-cycle/
- 使用快慢指针思想进行解决.
这里快慢指针的含义就是,比如说慢指针走一个,快指针走两个,如果要是又环的话,二者就是一定会相遇的. - 判断是否有环的过程之中,代码实现.
package 链表; public class _3_判断一个链表是否有环 {//141题 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) //这里是防止空指针异常的情况出现 { slow = slow.next; fast = fast.next.next; if(fast == slow) return true; } return false; } }
11 补充
- 这里需要进行注意的是remove方法之中存在首指针为0的情况,add方法之中也是需要进行注意:
12 虚拟头节点
- 使得代码更加的精简
- ?虚拟头节点的存在使得相应的add和remove以及toString方式存在差异.
- ArrayList2代码:
// // Source code recreated from a .class file by IntelliJ IDEA // (powered by Fernflower decompiler) // package com.mj; public class ArrayList2<E> extends AbstractList<E> { private E[] elements; private static final int DEFAULT_CAPACITY = 10; public ArrayList2(int capaticy) { capaticy = capaticy < 10 ? 10 : capaticy; this.elements = new Object[capaticy]; } public ArrayList2() { this(10); } public void clear() { for(int i = 0; i < this.size; ++i) { this.elements[i] = null; } this.size = 0; if (this.elements != null && this.elements.length > 10) { this.elements = new Object[10]; } } public E get(int index) { this.rangeCheck(index); return this.elements[index]; } public E set(int index, E element) { this.rangeCheck(index); E old = this.elements[index]; this.elements[index] = element; return old; } public void add(int index, E element) { this.rangeCheckForAdd(index); this.ensureCapacity(this.size + 1); for(int i = this.size; i > index; --i) { this.elements[i] = this.elements[i - 1]; } this.elements[index] = element; ++this.size; } public E remove(int index) { this.rangeCheck(index); E old = this.elements[index]; for(int i = index + 1; i < this.size; ++i) { this.elements[i - 1] = this.elements[i]; } this.elements[--this.size] = null; this.trim(); return old; } public int indexOf(E element) { int i; if (element == null) { for(i = 0; i < this.size; ++i) { if (this.elements[i] == null) { return i; } } } else { for(i = 0; i < this.size; ++i) { if (element.equals(this.elements[i])) { return i; } } } return -1; } private void ensureCapacity(int capacity) { int oldCapacity = this.elements.length; if (oldCapacity < capacity) { int newCapacity = oldCapacity + (oldCapacity >> 1); Object[] newElements = new Object[newCapacity]; for(int i = 0; i < this.size; ++i) { newElements[i] = this.elements[i]; } this.elements = newElements; System.out.println(oldCapacity + "扩容为" + newCapacity); } } private void trim() { int oldCapacity = this.elements.length; int newCapacity = oldCapacity >> 1; if (this.size <= newCapacity && oldCapacity > 10) { Object[] newElements = new Object[newCapacity]; for(int i = 0; i < this.size; ++i) { newElements[i] = this.elements[i]; } this.elements = newElements; System.out.println(oldCapacity + "缩容为" + newCapacity); } } public String toString() { StringBuilder string = new StringBuilder(); string.append("size=").append(this.size).append(", ["); for(int i = 0; i < this.size; ++i) { if (i != 0) { string.append(", "); } string.append(this.elements[i]); } string.append("]"); return string.toString(); } }一般不建议是使用添加虚拟头节点的方式进行.
13 复杂度分析(ArrayList)
- 复杂度的三种情况:
- 数组访问一个元素,速度是一致的,随机访问是非常快的. 数据规模是指元素的数量,O(n).
- 只有和数据规模相关的时候,才会分析相应的三种复杂度的情况.拿add方式进行分析,如下所示(remove方式是与add方式相同的):
最好的情况是:O(1),最坏情况是O(n),平均是O(n). - 链表的添加 删除的复杂度是O(1),是指添加 删除那一刻.
- 动态数组 链表复杂度分析
14 均摊度分析
- ?适用情况:经过连续的多次复杂度比较低的情况后，出现个别复杂度比较高的情况
15 ArrayList的缩容
- 当动态数组存在较多的容量的时候,就是需要进行一个缩容的操作.一般是存在相应的删除的过程.
private void trim() {
int oldCapacity = this.elements.length;
int newCapacity = oldCapacity >> 1;//首先是将原始的容量变成原始的一半,
if (this.size <= newCapacity && oldCapacity > 10) { //如果剩余的空间是原来的容量的一半,
Object[] newElements = new Object[newCapacity];//声明一个新的容量与数组
for(int i = 0; i < this.size; ++i) {
newElements[i] = this.elements[i];
}
this.elements = newElements;
System.out.println(oldCapacity + "缩容为" + newCapacity);
}
}16 复杂度震荡
- 如果要是扩容倍数和缩容时机设计不得当,会导致复杂度震荡.