数据对象:数据元素和元素个数(element[],size)
查找、删除、插入、扩容、缩容
而其他简单的算法，这里就不多做赘述仅列出所有算法(重要算法打了长*号)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
//基本操作
/**
* @param index 要添加的元素的索引
* @param element 要添加的元素
* 添加前要保证所添加的索引在0-size之间 因为顺序表的地址连续
*/
public void add(int index, E element);
/**
* @param index 索引
* @return 删除索引位置的数据元素
*/
public E remove(int index);
/**
* @param element 数据元素
* @return 查看某元素的索引
* 如果存在返回索引 不存在返回-1
*/
public int indexOf(E element);
/**
*缩容
*/
private void trim()
/**
*扩容
*/
private void ensureCapacity
/****************************************/
/**
* 清空List
*/
public void clear();
/**
* @return 返回顺序表中数据元素的数量
*/
public int size();
/**
* @return 判断该顺序表是否为空
*/
public boolean isEmpty();
/**
* @param element 要比较的element
* @return 判断顺序表中是否有该element
* 使用public int indexOf(E element)判断
*/
public boolean contains(E element);
/**
* @param element 在末尾插入该元素
*/
public void add(E element) ;
/**
* @param index 索引
* @return 获取索引位置的数据元素
*/
public E get(int index);
/**
*删除第一个出现的元素
* @param element 要删除的元素
*/
public void remove(E element);
/**
* @param index
* @param element
* @return 设置索引位置的元素为element并且返回原始元素
*/
public E set(int index, E element);
/**
*
* @return 返回规定的打印格式
*/
public String toString();
/**
* 默认初始化
*/
public SequenceList();
/**
*给定容量初始化
*/
public SequenceList(int Capacity)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
/**
算法描述
1.遍历2.找到返回元素索引找不到返回-1
存在的问题:是地址的比较不是对象内容的比较
*/
public int indexOf(E element) {
for (int i = 0; i < size; i++) {
if (elements[i] == element)
return i;
}
return ELEMENT_NOT_FOUND;
}
|
基本数据类型是直接在stack中存储的
![https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-01-08%20%E4%B8%8A%E5%8D%8810.09.28.png]( "截屏2022-01-08 上午10.09.28")
而对于范型而言，stack中存放的是的数据元素的地址，因为这个差异要改进算法如下:
改进:加入equals方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
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 (element.equals(elements[i]))
return i;
}
}
return ELEMENT_NOT_FOUND;
}
|
Average Search Length: n+1/2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
/**
算法分析:
1.判断删除位置是否合法
2.将想要删除的元素保留
3.将第i+1至第n位元素依次往前移动一个位置
4.表长减1，删除成功返回删除的元素
*/
public E remove(int index) {
if(index<0||index>=size)
{
throw new IndexOutOfBoundsException("索引超出范围：size=" + size + ",index=" + "index");
}
E old = elements[index];
for (int i = index; i < size-1; i++) {
elements[i]=elements[i+1];
}
size--;
return old;
}
|
改进：1.将索引检查进行封装2.加入缩容算法
1
2
3
4
5
6
7
8
9
10
11
|
public E remove(int index) {
RangeCheck(index);
trim();
E old = elements[index];
for (int i = index; i < size-1; i++) {
elements[i]=elements[i+1];
}
elements[size-1]=null;
size--;
return old;
}
|
Average Search Length: n-1/2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
/**
算法分析:
1.判断插入位置i是否合法
2.判断顺序表为n+1位置的储存空间是否已满，如果已满进行扩容
3.将第n至第i位的元素依次向后移动一个位置
4.将要插入的新元素e放到第i个位置
5.表长加1
*/
public void add(int index, E element) {
//如果索引没在0-size范围内 抛出添加异常
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("所添加索引超出范围：size=" + size + ",index=" + index);
}
//否则执行添加操作:可添加位置0-size
//先将index即以后的元素往后移动一位
for (int i = size; i > index; i--) {
elements[i] = elements[i-1];
}
elements[index]=element;
size++;
}
|
改进:1.将索引检查进行封装2.加入扩容算法
1
2
3
4
5
6
7
8
9
10
11
12
|
public void add(int index, E element) {
RangeCheckAdd(index);
ensuresCapacity(size+1);
for (int i = size; i > index; i--) {
elements[i] = elements[i-1];
}
elements[index]=element;
size++;
}
|
Average Search Length: n/2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
/**
算法分析:
1.将想要的容量作为参数传入method
2.将现有容量和想要有的容量进行比较，如果现有容量还够，则返回
3.如果不够，进行扩容
4.创建新容量的数组并进行挪动
5.将现有的数组指向新数组
*/
private void ensuresCapacity(int capacity)
{
int oldCapacity = elements.length; //初始为10
if(oldCapacity >= capacity) return;
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+"扩容到"+elements.length);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
/**
1.查看目前的容量
2.将目前容量和元素数量进行比较，如果目前容量不足够大，返回
3.如果太大，进行缩容
4.创建新容量的数组并进行挪动
5.将现有的数组指向新数组
*/
private void trim()
{
//先查看目前的容量
int OldCapacity =elements.length;
//将容量和size比较 如果OldCapacity小于2倍的size或者Capacity<DEFAULT_CAPACITY 不缩容
if (OldCapacity<(size<<1)||OldCapacity<DEFAULT_Capacity)
{
return;
}
//否则进行缩容量
int newCapacity = 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);
}
|
链表分为:(不/带)头node的单链表、双链表、循环单链表、循环双链表
因为jvm有自动清理垃圾的gc功能所以不再需要重写销毁链表的方法，而直接不要指向它即可
这里列出LinkList里所有的算法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
//基本操作
/**
初始化算法 不带头节点的默认初始化即可 带头节点的要显式初始化
*/
public LinkList()
{
}
/**
获取Node算法
*/
private Node<E> getNode(int index)
/**
* @param index 要添加的元素的索引
* @param element 要添加的元素
* 添加前要保证所添加的索引在0-size之间 因为顺序表的地址连续
*/
public void add(int index, E element);
/**
* @param index 索引
* @return 删除索引位置的数据元素
*/
public E remove(int index);
/**
* @param element 数据元素
* @return 查看某元素的索引
* 如果存在返回索引 不存在返回-1
*/
public int indexOf(E element);
/**
* 清空List
*/
public void clear();
/**
* @return 返回顺序表中数据元素的数量
*/
public int size();
/**
* @return 判断该顺序表是否为空
*/
public boolean isEmpty();
/**
* @param element 要比较的element
* @return 判断顺序表中是否有该element
* 使用public int indexOf(E element)判断
*/
public boolean contains(E element);
/**
* @param element 在末尾插入该元素
*/
public void add(E element) ;
/**
* @param index 索引
* @return 获取索引位置的数据元素
*/
public E get(int index);
/**
*删除第一个出现的元素
* @param element 要删除的元素
*/
public void remove(E element);
/**
* @param index
* @param element
* @return 设置索引位置的元素为element并且返回原始元素
*/
public E set(int index, E element);
/**
*
* @return 返回规定的打印格式
*/
public String toString();
/**
* 默认初始化
*/
public SequenceList();
/**
*给定容量初始化
*/
public SequenceList(int Capacity)
|
数据对象:Node()、元素个数size、头指针first，不需要显示初始化链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
private Node<E> getNode(int index)
{
//检查索引的合法性
RangeCheck(index);
//获取首元节点
Node<E> node =first;
for (int i = 0; i < index; i++) {
//第index个node 需要next index次
node = node.next;
}
return node;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
/**
算法分析:
1.获取首元节点
2.循环查找获取想要的节点
3.通过equals方法进行比较获取到的node 找不到 返回-1
4.为element == null特殊化处理
*/
public int indexOf(E element) {
//先判断element是否为null
if(element == null)
{
//遍历
//创建首元节点
Node<E> node = this.first;
//n个node 遍历需要n次
for (int i = 0; i < size; i++) {
if (node.element==null)
return i;
node = node.next;
}
}
else
{
//遍历
//创建首元节点
Node<E> node = this.first;
//n个node 遍历需要n-1次
for (int i = 0; i < size; i++) {
if (element.equals(node.element))
return i;
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
/**
算法分析:
1.判断插入位置i是否合法
2.先找到原始Nodei-1的储存位置(自带索引检查)和原始Nodei的储存位置
3.创建新的节点:(
新节点的指针域指向Nodei
Nodei-1的指针域指向新节点
4.考虑首未情况(只需要考虑首)添加代码
5.size++；
*/
public void add(int index, E element) {
//这
RangeCheckAdd(index);
if (index == 0)
{
//创建新node
//创建时右边的this.first ==null
//然后放入一个元素
this.first = new Node<>(element, this.first);
}
else
{
//自带RangeCheck 上一个node的范围只能是0到size-1
Node<E> pre = getNode(index - 1);
//插入
pre.next = new Node<>(element,pre.next);
}
size++;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
/**
算法分析:
1.获取Nodei-1(自带索引检查)和原始Nodei的位置
2.将Nodei-1的指针指向原始节点的下一个Node
3.考虑index为0的情况
4.size--并返回删除的node
*/
public E remove(int index) {
Node<E> node = this.first;
if(index == 0)
{
//和this.first = this.first.next 效果一样 不过像下面这样写更容易理解
this.first = first.next;
}
else
{
//自带索引越界检查
Node<E> pre = getNode(index - 1);
node = pre.next;
//很精妙的node设计 既简化了代码 更容易看懂了
pre.next = node.next;
}
size--;
return node.element;
}
|
数据对象:Node()、元素个数size、头指针first，不再需要特殊考虑index==0的位置，但要显式初始化空链表
1
2
3
4
5
6
|
/**
算法分析:创建新node，并将first指针指向它
*/
public LinkList() {
first = new Node<>(null,null);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
/**
1.索引合法性检查
2.获取首元节点
3.遍历查找索引处的Nodei
4.返回Nodei
*/
private Node<E> getNode(int index)
{
//检查索引的合法性
RangeCheck(index);
//获取首元节点,此时的首元node从first变为了first.next
Node<E> node =first.next;
for (int i = 0; i < index; i++) {
//第index个node 需要next index次
node = node.next;
}
return node;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
/**
算法分析:
1.判断插入位置i是否合法
2.先找到原始Nodei-1的储存位置(自带索引检查)和原始Nodei的储存位置
3.创建新的节点:(
新节点的指针域指向Nodei
Nodei-1的指针域指向新节点
4.size++；
*/
public void add(int index, E element) {
//这里要手动RangeCheckAdd
RangeCheckAdd(index);
Node<E> pre = (index==0)? first : getNode(index - 1);
pre.next = new Node<>(element,pre.next);
size++;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
/**
算法分析:
1.获取首元节点
2.循环查找获取想要的节点
3.通过equals方法进行比较获取到的node 找不到 返回-1
4.为element == null特殊化处理
*/
public int indexOf(E element) {
//先判断element是否为null
if(element == null)
{
//遍历
//创建首元节点
Node<E> node = this.first.next;
//n个node 遍历需要n次
for (int i = 0; i < size; i++) {
if (node.element==null)
return i;
node = node.next;
}
}
else
{
//遍历
//创建首元节点
Node<E> node = this.first.next;
//n个node 遍历需要n-1次
for (int i = 0; i < size; i++) {
if (element.equals(node.element))
return i;
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
/**
算法分析:
1.获取Nodei-1(自带索引检查)和原始Nodei的位置
2.将Nodei-1的指针指向原始节点的下一个Node
不用考虑index为0的情况
3.size--;
*/
public E remove(int index) {
//自带索引越界检查
Node<E> prevNode = getNode(index - 1);
Node<E> node = prevNode.next;
Node<E> nextNode = node.next;
prevNode.next = nextNode;
size--;
return node.element;
}
|
数据对象:Node()（E element, next）、元素个数size、头指针Node first
后续还可以添加:
1
2
3
4
5
|
Node<E> current //现在所指的node
public void reset(); //将current指针指向首元节点
public E next(); //将current指针往下移动一个并输出移动后的Node中的element
public E remove(); //删除并输出当前的Node并将指针往下移动
|
使用隐式初始化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
/**
1.索引合法性检查
2.获取首元节点
3.遍历查找索引处的Nodei
4.返回Nodei
*/
private Node<E> getNode(int index)
{
//检查索引的合法性
RangeCheck(index);
//获取首元节点,此时的首元node从first变为了first.next
Node<E> node =first;
for (int i = 0; i < index; i++) {
//第index个node 需要next index次
node = node.next;
}
return node;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
/**
算法分析:
1.判断插入位置i是否合法
2.先找到原始Nodei-1的储存位置(自带索引检查)和原始Nodei的储存位置
3.创建新的节点:(
新节点的指针域指向Nodei
Nodei-1的指针域指向新节点
4.考虑首未情况(只需要考虑首)添加修改代码
考非空链表首元Node插入：
获取最后一个Node
创建新的Node并将新Node到指针指向原始的第一个Node
将头指针指向新创建的Node
将最后一个Node的指针指向新Node
考虑空链表插入：
创建新的Node并将新Node到指针指向头指针
将头指针指向新Node
5.size++；
*/
public void add(int index, E element) {
RangeCheckAdd(index);
if (index == 0)
{
//创建新node指针指向原始的第一个Node 并 将指针first指向新node
this.first = new Node<>(element, this.first);
if(size==0)
{
first.next = first
}
{
//获取最后一个Node
new Node<E> lastNode = getNode(size - 1);
//将最后一个Node指针指向新创建的Node
lastNode.next = first;
}
}
else
{
//自带RangeCheck 上一个node的范围只能是0到size-1
Node<E> pre = getNode(index - 1);
//插入
pre.next = new Node<>(element,pre.next);
}
size++;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
/**
算法分析:
1.获取首元节点
2.循环查找获取想要的节点
3.通过equals方法进行比较获取到的node 找不到 返回-1
4.为element == null特殊化处理
*/
public int indexOf(E element) {
//先判断element是否为null
if(element == null)
{
//遍历
//创建首元节点
Node<E> node = this.first;
//n个node 遍历需要n次
for (int i = 0; i < size; i++) {
if (node.element==null)
return i;
node = node.next;
}
}
else
{
//遍历
//创建首元节点
Node<E> node = this.first;
//n个node 遍历需要n-1次
for (int i = 0; i < size; i++) {
if (element.equals(node.element))
return i;
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
/**
算法分析:
1.获取Nodei-1(自带索引检查)和原始Nodei的位置
2.将Nodei-1的指针指向原始节点的下一个Node
3.考虑index为0的情况
考虑有1个以上的Node的删除
考虑只有一个Node的删除
4.size--并返回删除的node
*/
public E remove(int index) {
Node<E> node = this.first;
if(index == 0)
{
if(size == 1)
{
first = null;
}
else
{
//获取最后一个Node
Node<E> lastNode = getNode(size-1);
this.first = first.next;
lastNode.next = first;
}
}
else
{
//自带索引越界检查
Node<E> pre = getNode(index - 1);
node = pre.next;
//很精妙的node设计 既简化了代码 更容易看懂了
pre.next = node.next;
}
size--;
return node.element;
}
|
数据对象:Node()（E element, next）、元素个数size、头指针Node first，尾指针Nodelast
隐式初始化即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
/**
1.索引合法性检查
2.获取首元节点
3.获取最后一个Node
4.通过两种方法遍历查找索引处的Nodei
index<(size>>1)
index>(size>>1)
5.返回Nodei
*/
private Node<E> getNode(int index)
{
//检查索引的合法性
RangeCheck(index);
if (index<(size>>1))
{
//获取首元节点
Node<E> node =first;
for (int i = 0; i < index; i++) {
//第index个node 需要next index次
node = node.next;
}
return node;
}
//************从后往前***************
else
{
//获取最后一个节点
Node<E> node = this.last;
for (int i = size-1; i > index; i--) {
node = node.prev;
}
return node;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
/**
算法分析:
1.判断插入位置i是否合法
2.先找到原始Nodei的储存位置 再找到prevNode的存储位置
3.创建新的节点:(
新节点的next指针域指向原始Nodei prev指针指向prevNode prevNode的next指针域指向新节点(一次性完成)
原始Nodei的prev指针指向新Node
4.考虑首未情况添加修改代码
先考虑首元Node
考非空de插入：
获取原始首元节点
创建新node并将next指针指向原始首元节点 将prev指针指向null
将原始首元节点的prev指针指向新node
将头指针first指向新node
考虑空链表插入：
获取原始首元节点 null
创建新node并将next指针指向原始首元节点(null) 将prev指针指向null
将头指针尾指针都指向新node
5.考虑在尾巴插入
5.size++；
*/
public void add(int index, E element) {
RangeCheckAdd(index);
//首节点插入和空链表插入
if (index == 0)
{
//获取原始首元节点
Node<E> node = first;
Node<E> nextNode = node;
Node<E> newNode= new Node<>(null,element,nexNode);
if(size == 0)
{
first = newNode;
last = newNode;
}
else
{
first = newNode;
nextNode.prev = newNode;
}
}
//普通插入和在尾巴上插入
else
{
if(index == size)
{
Node<E> prevNode = this.last;
Node<E> newNode = new Node<>(prevNode, element, null);
last = newNode;
}
else
{
//自带RangeCheck 上一个node的范围只能是0到size-1
Node<E> node = getNode(index);
Node<E> prevNode = node.prev;
Node<E> nextNode = node;
Node<E> newNode= new Node<>(prevNode,element,nexNode);
//插入
prevNode.next = newNode;
nextNode.prev = newNode;
}
size++;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
/**
算法分析:
1.获取首元节点
2.循环查找获取想要的节点
3.通过equals方法进行比较获取到的node 找不到 返回-1
4.为element == null特殊化处理
*/
public int indexOf(E element) {
//先判断element是否为null
if(element == null)
{
//遍历
//创建首元节点
Node<E> node = this.first;
//n个node 遍历需要n次
for (int i = 0; i < size; i++) {
if (node.element==null)
return i;
node = node.next;
}
}
else
{
//遍历
//创建首元节点
Node<E> node = this.first;
//n个node 遍历需要n-1次
for (int i = 0; i < size; i++) {
if (element.equals(node.element))
return i;
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
/**
算法分析:
1.获取原始Nodei的位置 获取Nodei的上一个node和下一个node
2.将Nodei-1的next指针指向原始节点的下一个Node
将Nodei+1的prev指针指向原始节点的上一个节点
3.考虑index为0的情况
获取原始的首元Node
获取原始首元节点的下一个Node
4.size--并返回删除的node
*/
public E remove(int index) {
//自带索引越界检查
Node<E> node = getNode(index);
Node<E> prevNode =node.prev;
Node<E> nextNode = node.next;
if（prevNode == null）
{
if（nextNode == null）
{
first =null;
last =null;
}
else{
first =nextNode;
nextNode.prev = null;
}
}
else
{
prevNode.next = nextNode;
nextNode.prev = prevNode;
return node.element;
}
size--;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
/**
算法分析:
1.索引越界检查
2.考虑一般情况
3.考虑index位置插入
4.考虑空链表
5.考虑第一个位置插入且不是空链表
*/
//索引合法检查
RangeCheckAdd(index);
//如果现在是空链表或者插入最后一个位置
if (index == size)
{
//如果是空链表
if (first == null)
{
Node<E> newNode = new Node<>(null, element, null);
first = newNode;
last = newNode;
newNode.next = newNode;
newNode.prev = newNode;
}
//如果插入最后一个元素
else
{
Node<E> node = getNode(0);
Node<E> nextNode = node;
Node<E> prevNode = node.prev;
Node<E> newNode = new Node<>(prevNode, element, nextNode);
prevNode.next =newNode;
nextNode.prev = newNode;
//将last指向newNode
last = newNode;
}
}
else
{
//考虑一般情况
Node<E> node = getNode(index);
Node<E> nextNode = node;
Node<E> prevNode = node.prev;
Node<E> newNode = new Node<>(prevNode, element, nextNode);
prevNode.next =newNode;
nextNode.prev = newNode;
//如果插入位置是index=0且不是空链表
if (index == 0)
first = newNode;
}
size++;
RangeCheckAdd(index);
//考虑空链表和向最后一个添加的情况
if (index == size) {
//将最后的那个node指定为prevNode
//Node<E> prevNode = getNode(index - 1);
Node<E> prevNode = this.last; //null
//获取首元节点
Node<E> firstNode = this.first;
//创建新的node
Node<E> newNode = new Node<>(prevNode, element, firstNode);
//将last指向新的node
this.last = newNode;
//考虑空链表的情况
if (this.first == null) {
//first = last
this.first = newNode;
//考虑添加第size个元素的情况
newNode.prev = newNode;
newNode.next = newNode;
} else
{
//将prevNode的next指向新节点
prevNode.next = newNode;
//将第一个node的prev指向新添加的最后一个node
firstNode.prev = newNode;
}
}
//考虑普通添加和添加在第一个位置的情况
else
{
Node<E> oldNode = getNode(index);
Node<E> nextNode = oldNode;
Node<E> lastNode = getNode(size - 1);
//oldNode的前一个node 变为了prevNode
Node<E> prevNode = oldNode.prev;
Node<E> newNode = new Node<>(prevNode, element, nextNode);
//接线 接prevNode的next线 和nextNode的prev线
nextNode.prev = newNode;
//考虑添加第一个的情况
//因为是循环链表 所以prevNode是lastNode
if (prevNode == lastNode)
{
first =newNode;
last = lastNode;
lastNode.next =nextNode;
}
//考虑普通添加的情况
else
{
prevNode.next = newNode;
}
}
size++;
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
/**
算法分析:
循环还是比较好写的 一般情况和删除第一个最后一个时的区别主要是后者需要进行头尾指针的挪动
1.考虑一般情况
2.考虑唯一元素的删除
3.最前面和最后面的删除(加条件)
*/
private E remove(Node<E> node)
{
//删除唯一的元素
if (node.next == node)
{
first = null;
last = null;
}
else
{
//考虑一般情况的删除
Node<E> nextNode = node.next;
Node<E> prevNode = node.prev;
nextNode.prev =prevNode;
prevNode.next = nextNode;
if (node == getNode(0)) first=nextNode;
if(node == getNode(size -1)) last = prevNode;
}
size--;
return node.element;
}
|
