热门标签
热门文章
- 1gerrit submit撤回_Gerrit使用篇-提交代码，合并代码
- 2《图解密码技术》笔记_图解密码技术学习笔记
- 3算法体系-02第二 时间复杂分析（插入/冒泡/选择/二分）
- 4GitHub Actions入门教程
- 5基于neo4j的体育运动员问答问答系统_neo4j智慧问答
- 6体验文心一言AI大模型生成农行、苏行和南京银行报告_利用大模型生成报告
- 7Android中免root的hook框架Legend原理解析_simhook模块免root
- 8火狐浏览器firefox检测不到U盾证书
- 9C#程序变量统一管理例子 - 开源研究系列文章
- 10若依 验证码出不来 Fontconfig head is null, check your fonts or fonts configuration
当前位置: article > 正文
ArrayList和LinkedList中的单链表，双向链表模拟实现其方法功能；_arraylistlist 单向链表
作者：AllinToyou | 2024-05-29 12:49:49
赞
踩
arraylistlist 单向链表
Hello大家好，今天带来的是对于顺序表、单链表、双向链表的模拟实现，主要对于其常用的API方法进行实现。
对于ArrayList和LinkedList大家可以详细观看这篇文章：
实现List接口的ArrayList和LinkedList
话不多说，接下来就进入正题吧！
###ArrayList的模拟实现
接下来简单分享一下每个方法实现思路
首先构建数组（用来存放元素），构建一个空的int类型的数据（用来确定数据）
创建两个构造方法，一个带参数，一个不带参数。
对于该链表实现扩容机制。扩容机制详情参考下面代码，或者上面的博客。
实现重写toString方法，实现对于下标越界的判断。
具体的api:
尾插：容量+1，直接将元素放在数组最后，元素数量+1
元素插入index位置：确保下标不越界，扩容，从最后到index位置移动元素，再下标index位置赋值，元素数量+1
删除index位置元素：确保下标不越界，删除该元素，之后元素整体往前移动。 元素数量-1
删除遇到的第一个元素：找到元素的下标，直接调用删除index位置方法。 元素数量-1
获取index位置元素：确保下标不越界，直接返回该元素
将index位置修改为新元素：确保下标不越界，直接进行重新赋值
清空：每个值赋值为null
返回第一个o所在的位置：判断是否为空，按照条件进行遍历
返回最后一个o所在的位置：判断是否为空，从后往前遍历寻找
截取部分List：判断数据是否正常，重新构造链表进行遍历赋值，返回该链表。
具体实现请看下面代码：
//ArrayList模拟实现 底层为数组实现 public class MyArrayList<E> { private Object[] array; private int size; public MyArrayList(){} //构造方法，initCapaCity为所需容量。 public MyArrayList(int initCapacity){ if (initCapacity>0){ array=new Object[initCapacity]; }else if (initCapacity==0){ array=new Object[0]; }else { throw new IllegalArgumentException("容量为负数"); } } public int size(){ return size; } public boolean empty(){ return size==0; } //扩容 private static final int Max_Array_Size=Integer.MAX_VALUE-8; private void ensureCapacity(int initCapacity){ int oldCapacity = array.length; //1.5倍扩容 int newCapacity =oldCapacity+(oldCapacity>>1); //新的容量比所需容量小时，替换为新的容量 if (newCapacity<initCapacity){ newCapacity=initCapacity; } //不能超出数据类型的最大值 if (newCapacity>Max_Array_Size){ newCapacity=Max_Array_Size; } array= Arrays.copyOf(array,newCapacity); } //下标是否越界 private void rangeCheck(int index){ if (index<0||index>=size){ throw new IndexOutOfBoundsException("越界"); } } //插入操作时数组下标是否越界 private void rangeCheckForAdd(int index){ if (index>size){ throw new IllegalArgumentException("add下标数组越界"); } } @Override public String toString() { String s="["; if(size > 0){ for (int i = 0; i < size-1; i++) { s += array[i]; s += ", "; } s += array[size-1]; } s += "]"; return s; } //List实现的方法 //尾插 public boolean add(E e){ //确保容量 ensureCapacity(size+1); //先使用size值 然后在size++ array[size++]=e; return true; } //将e插入到index为位置 public void add(int index ,E element){ //检查是否越界 rangeCheckForAdd(index); ensureCapacity(size+1); //将元素后移插入//数组下标为index 从0开始计算 for (int i=size-1;i>=index;i--){ array[i+1]=array[i]; } array[index]=element; size++; } //删除index位置元素 public E remove(int index){ rangeCheck(index); E e=(E) array[index]; for (int i = index+1; i < size; i++) { array[i-1]=array[i]; } size--; return e; } //删除遇到的第一个O public boolean remove (Object o){ int index=indexOf(o); if (index==-1){ return false; } remove(index); return true; } //获取下标 index 位置元素 public E get(int index){ rangeCheck(index); return (E) array[index]; } //将下标 index 位置元素设置为 element public E set(int index , E element){ rangeCheck(index); array[index] =element; return element; } //清空 public void clear(){ for (int i = 0; i <size; i++) { array[i]=null; } size=0; } //判断O是否在线性表中 public boolean contains(Object O){ return indexOf(O)>0; } //返回第一个O所在的下标 public int indexOf(Object o){ if (o==null){ for (int i = 0; i <size; i++) { if (array[i]==null){ return i; } } }else { for (int i = 0; i <size; i++) { if (o.equals(array[i])){ return i; } } } return -1; } //返回最后一个O所在的下标 public int lastIndexOf(Object o){ if (o==null){ //i=size会越界 长度为size 下标到size-1 for (int i = size-1; i >=0 ; i--) { if (array[i]==null){ return i; } } }else { for (int i = size-1; i >=0 ; i--) { if (array[i].equals(o)){ return i; } } } return -1; } //截取部分List MyArrayList<E> subList (int fromIndex ,int toIndex){ if (toIndex-fromIndex<0){ throw new IllegalArgumentException("参数有误"); } MyArrayList<E> list=new MyArrayList<>(toIndex-fromIndex); for (int i = fromIndex; i <toIndex; ++i) { list.add((E) array[i]); } return list; } 验证上述方法： public static void main(String[] args) { MyArrayList<Integer> arrayList=new MyArrayList<>(3); arrayList.add(1); arrayList.add(2); arrayList.add(3); arrayList.add(4); System.out.println(arrayList.size()); System.out.println(arrayList); arrayList.add(0,0); if(arrayList.contains(5)){ arrayList.add(5); } arrayList.add(0); System.out.println(arrayList); System.out.println(arrayList.indexOf(0)); System.out.println(arrayList.lastIndexOf(0)); System.out.println(arrayList.subList(2, 5)); arrayList.remove(0); System.out.println(arrayList); arrayList.clear(); System.out.println(arrayList); } }
- 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
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
Linked的模拟实现
单链表的实现
对于单链表的实现，需要先构建其每个节点的特性，节点中存放下一个元素的位置，和当前元素的值，实现其构造方法。传入头节点，即可对方法进行实现
具体的实现方法：
尾插：构建新节点，判断是否是空链表进行插入，空则直接插入，不为空则进行遍历获取其最后的节点插入
头插：直接进行插入即可
任意位置插入：确保下标不越界，对于位置进行判断，如果为首位置，直接头插，在中间位置则进行遍历后插入，更新前一个节点和当前节点保存的地址信息
删除第一次出现元素 e 的地方：对于链表进行遍历，找到该元素后进行删除，更新前一个元素的地址信息
删除所有元素为 e 的地方：对于元素进行遍历，对于头节点和其他位置节点做不同的删除方式，最后更新地址即可。
查找关键字是否存在：对于链表进行遍历查询进行结果返回。
链表的长度：遍历后直接返回遍历的次数。
具体实现：
//单链表 public class MySingleLinkList<E> { public static class Node<E>{ E value; Node<E> next; public Node(E value){ this.value=value; } } //Head 指向链表中的一个有效的节点 Node<E> head; //尾插法 public void addLast(E data){ Node<E> newNode=new Node(data); if(head==null){ //头结点为空 head=newNode; }else { //找到最后一个节点 Node<E> cur=head; while (cur.next!=null){ cur=cur.next; } //循环结束找到最后一个节点 cur.next=newNode; } } //头插法 public void addFirst(E data){ Node<E> newNode=new Node<>(data); /* if (head==null){ //直接插入 head=newNode; }else { //插入到头结点的前面 newNode.next=head; head=newNode; }*/ //总结优化 newNode.next=head; head=newNode; } //任意位置插入,第一个数据节点为0号下标 public boolean addIndex(int position, E data){ //检测下标是否越界 if (position<0||position>=size()){ throw new IllegalArgumentException("addIndex:position非法"); } if (0==position){ addFirst(data); return true; } //找到index的位置 Node<E> cur=head; Node<E> prev=null; while (0!=position){ prev=cur; cur=cur.next; position--; } //找到位置插入节点 Node<E> newNode=new Node<>(data); prev.next=newNode; newNode.next=cur; return true; } //删除第一次出现关键字key的地方 public void remove(E e){ Node<E> cur=head; Node<E> prev=null; while (cur!=null){ if (cur.value.equals(e)){ cur.value=null; if (prev==null){ //表示为头结点 head=cur.next; }else{ //对于非头结点的节点进行删除 prev.next=cur.next; } return; } prev=cur; cur=cur.next; } } //删除所有值为Key的节点 public void removeAllKey(E e){ //法1： Node<E> cur=head; Node<E> prev=null; while (cur!=null){ if (e.equals(cur.value)){ //删除节点 cur.value=null; //头结点的情况 if (prev==null){ head=cur.next; cur=head; }else{ prev.next=cur.next; cur=prev.next; } }else{ prev=cur; cur=cur.next; } } //法2：//但是时间太长为O（N^2） /* while (contains(e)){ remove(e); }*/ } //查找是否包含关键字e在单链表中 public boolean contains(E e){ Node<E> cur=head; //遍历 while (cur!=null){ if (cur.value.equals(e)){ return true; } cur=cur.next; } return false; } //得到链表的长度 public int size(){ Node<E> cur=head; int count=0; while (cur!=null){ count++; cur=cur.next; } return count; } //toString方法 @Override public String toString() { String s="["; Node<E> cur=head; while (cur!=null){ s+=cur.value; if (null!=cur.next){ s+=","; } cur=cur.next; } s+="]"; return s; } //测试方法 public static void main(String[] args) { MySingleLinkList<Integer> myLinkedList=new MySingleLinkList<>(); myLinkedList.addFirst(2); myLinkedList.addFirst(1); myLinkedList.addFirst(0); myLinkedList.addLast(3); myLinkedList.addLast(4); myLinkedList.addLast(5); System.out.println(myLinkedList); System.out.println(myLinkedList.size()); myLinkedList.addIndex(4,9); System.out.println(myLinkedList); myLinkedList.remove(3); System.out.println(myLinkedList); myLinkedList.addIndex(2,2); myLinkedList.addIndex(2,2); System.out.println(myLinkedList); myLinkedList.removeAllKey(2); System.out.println(myLinkedList); System.out.println(myLinkedList.contains(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
- 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
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
双向链表的实现
首先双向链表的节点结构信息：保存的元素，前一个元素的地址，后一个元素的地址。
传入头节点和尾节点进行实现
头插：创建新的节点，对于插入位置进行判断，最后更新地址信息
尾插：创建新的节点，对于插入位置进行判断，非头插则进行遍历后更新前一个元素和当前元素下一个元素的地址信息。
元素插入index位置：确保不会越界，进行头插或者遍历到index位置插入，最后更新元素的地址信息。
查询是否包含关键字 e：调用查询e元素下标的方法进行返回值的判断。
从前往后找第一个e：遍历查询，返回信息
从后往前找第一个e：从后往前进行遍历，返回信息
删除第一个元素：遍历后进行判断，如果存在就删除。
删除所有的元素：对于头节点和子节点的删除进行分开处理，最后对于元素地址信息进行更新即可。
获取链表的长度：遍历元素获取结果。
清空链表：整体进行删除。
public class MyLinkedList<E> { //双向链表的节点结构 public static class ListNode<E>{ E element; ListNode<E> next; ListNode<E> prev; public ListNode(E e){ element=e; } } //双向链表的成员变量 ListNode<E> first; ListNode<E> last; int size=0; //LinkedList实现的方法 //头插 public void addFirst(E e){ ListNode<E> newNode=new ListNode<>(e); if (first==null){ //直接插入 last=newNode; }else { //表示头结点不为空 first.prev=newNode; newNode.next=first; newNode.prev=null; } first=newNode; size++; } //尾插 public void addLast(E e){ ListNode<E> newNode= new ListNode<>(e); if (first==null){ //头结点为空直接插入 first=newNode; }else{ //不为空 last.next=newNode; newNode.prev=last; } last=newNode; size++; } //将e插入到index为位置 public boolean addIndex(int index ,E e){ if (index<0||index>=size()){ throw new IllegalArgumentException("地址越界") } ListNode<E> newNode=new ListNode<>(e); ListNode<E> cur=first; ListNode<E> prev=null; if (index==0){ newNode.next=cur; newNode.prev=null; cur.prev=newNode; return true; } //TODO 待确认信息 while (index!=0){ prev=cur; cur=cur.next; index--; } //插入元素 prev.next=newNode; newNode.prev=prev; newNode.next=cur; cur.prev=newNode; size++; return true; } //查找是否包含关键字 e 是否在单链表当中 public boolean contains(E e){ return indexOf(e)!=-1; } public int indexOf(E e){ ListNode<E> cur=first; int index=0; //遍历链表 while (cur!=null){ if (e.equals(cur.element)){ return index; } index++; cur=cur.next; } return -1; } //从后往前找 public int lastIndexOf(E e){ ListNode<E> cur=last; int index=size()-1; while (cur!=null){ if (e.equals(cur.element)){ return index; } index--; cur=cur.prev; } return -1; } //删除第一次出现关键字为key的节点 public void remove(E e){ ListNode<E> cur=first; ListNode<E> prev=null; while (cur!=null){ if (cur.element.equals(e)){ cur.element=null; prev.next=cur.next; cur=prev.next; cur.prev=prev; size--; return; } prev=cur; cur=cur.next; } } //删除所有值为key的节点 public void removeAllKey(E key){ ListNode<E> cur=first; ListNode<E> prev=null; while (cur!=null){ if (cur.element.equals(key)){ cur.element = null; //节点在头的位置 if (prev==null) { cur = cur.next; cur.prev = null; }else { //其他的位置遇到该元素 prev.next=cur.next; cur=cur.next; cur.prev=prev; } size--; }else { prev=cur; cur=cur.next; }} } //得到单链表的长度 public int size(){ ListNode<E> cur=first; int count=0; while (cur!=null){ count++; cur=cur.next; } return count; } @Override public String toString(){ String s="["; if (first==null){ s+="]"; return s; } ListNode<E> cur = first; while (cur.next!=null){ s+=cur.element; s+=","; cur=cur.next; } s+=cur.element; s+="]"; return s; } public void clear(){ first=null; last=null; } // public static void main(String[] args) { MyLinkedList<Integer> myLinkedList=new MyLinkedList<>(); myLinkedList.addFirst(2); myLinkedList.addFirst(1); myLinkedList.addFirst(0); myLinkedList.addLast(3); myLinkedList.addLast(4); myLinkedList.addLast(5); System.out.println(myLinkedList); System.out.println(myLinkedList.size()); myLinkedList.addIndex(4,9); System.out.println(myLinkedList); myLinkedList.remove(3); System.out.println(myLinkedList); System.out.println(myLinkedList.lastIndexOf(4)); myLinkedList.addIndex(2,2); myLinkedList.addIndex(2,2); System.out.println(myLinkedList); myLinkedList.removeAllKey(2); System.out.println(myLinkedList); System.out.println(myLinkedList.contains(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
- 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
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/642205
推荐阅读
相关标签
