欢迎关注个人主页：逸狼
创造不易，可以点点赞吗~
如有错误，欢迎指出~
目录
顺序表的缺点
链表
模拟实现链表
创建MySingleLidnkedList类和测试类Test
定义节点和创建链表的方法
测试
结果
打印链表和求链表长度
测试
结果
头插法
测试
结果
尾插法
任意位置插入
测试
结果
删除任意值val
测试
结果
删除所有val值
测试
结果
清空链表
顺序表的缺点
对于ArrayList来说，不方便插入和删除，因为要移动元素。比如，最坏的情况：0下标插入，删除0下标，都要移动所有元素。
扩容可能会浪费空间，假设100个空间，要放101个数据（进行1.5倍扩容，得150个空间），但实际只放了101个，剩下49个空间就浪费了
为了解决以上问题：链表他来了~
链表
有八种结构
- 链表结构在逻辑上是连续的，但物理上不一定连续
- 现实中的节点一般是从堆上申请的
模拟实现链表
创建MySingleLidnkedList类和测试类Test
定义节点和创建链表的方法
public class MySingleLinkedList { //定义节点类 内部类 class ListNode{ public int val; public ListNode next; public ListNode(int val){ this.val=val; } } public ListNode head;//代表链表的头节点 public void createList(){ //node1等为局部变量 当createList调用完之后，会node1等会消失 ListNode node1=new ListNode(12); ListNode node2=new ListNode(23); ListNode node3=new ListNode(34); ListNode node4=new ListNode(45); ListNode node5=new ListNode(56); node1.next=node2; node2.next=node3; node3.next=node4; node4.next=node5; node5=null; this.head=node1; } }测试
MySingleLinkedList msl=new MySingleLinkedList(); msl.createList();//创建好了五个节点的链表结果
打印链表和求链表长度
有两个问题
1 怎么从第一个节点走到第二个节点
head=head.next
2 链表什么时候遍历完
head==null（若条件是 head.next==null则会导致最后一个节点不会打印）
打印链表 public void display(){ ListNode cur=head; while(cur!=null){ System.out.print(cur.val+" "); cur=cur.next; } System.out.println(); } //求链表长度 public int size(){ int count=0; ListNode cur=head; while(cur!=null){ count++; cur=cur.next; } return count; }测试
msl.display(); System.out.println(msl.size());结果
头插法
先实例化一个节点，将数据放入节点。
- node.next=head;
- head=node;
（插入数据时一般先绑后面，防止数据丢失）
注意：空链表时也可以使用该代码，因为node.next和head本身都为空，所以不影响；
//头插法 public void addFirst(int val){ ListNode node=new ListNode(val); node.next=head; head=node; }测试
msl.addFirst(1); msl.addFirst(4); msl.addFirst(3); msl.addFirst(2);结果
尾插法
需要找到链表的尾巴（假设找到的尾节点是cur）
- 遍历（进入while循环）条件是cur.next!=null（想象此时cur是最后一个节点，cur.next==null,不能进入循环，即cur找到了尾节点）
- cur=cur.next;
cur.next=node
//尾插法 public void addLast(int val){ ListNode node=new ListNode(val); if(head==null){ head=node; return; } ListNode cur=head; while(cur.next!=null){ cur=cur.next; } cur.next=node; }任意位置插入
先找到index-1位置的节点（假设是节点cur）
- node.next=cur.next
- cur.next=node
还要注意以下特殊情况
- index==0 ->头插
- index==len->尾插
- index非法（index<0和index>链表长度）情况，此时可以抛出异常（自己定义的）
//任意位置插入 public void addIndex(int index,int val){ //1.判断index的合法性 try{ findIndexSubOne(index); }catch(IndexNotLegalException e){ e.printStackTrace(); } // 2.index==0||index==size(); if(index==0){ addFirst(val); return; } if(index==size()){ addLast(val); return; } ListNode node=new ListNode(val); // 3.找到Index前一个位置 ListNode cur=findIndexSubOne(index); // 链接 node.next=cur.next; cur.next=node; } //找Index前一个位置 private ListNode findIndexSubOne(int index) { ListNode cur=head; for (int i = 0; i < index-1; i++) { cur=cur.next; } return cur; } //判断Index是否合法 private void checkIndex(int index)throws IndexNotLegalException{ if(index<0||index>size()){ throw new IndexNotLegalException("Index不合法。。。"); } }测试
msl.addFirst(4); msl.addFirst(3); msl.addFirst(2); msl.addFirst(1); msl.display(); msl.addIndex(0,9); msl.display(); msl.addIndex(2,99); msl.display(); msl.addIndex(msl.size(), 999); msl.display();结果
删除任意值val
利用循环条件cur.next！=null找到值为val的前一个节点
找到cur后,定义被删的节点del=cur.next,让cur.next=del.next,完成删除操作
注意
- 处理空链表：判断head为空后，直接return
- 处理头节点是要删的节点：head=head.next;
//删值为val的值 public void remove(int val){ if(head==null){ return; } //删头节点 if(head.val==val){ head=head.next; return; } //找到val前一个节点 ListNode cur=head; while(cur.next!=null){ if(cur.next.val==val){ ListNode del=cur.next; cur.next=del.next; return; } cur=cur.next; } }测试
MySingleLinkedList msl=new MySingleLinkedList(); msl.addLast(11); msl.addLast(22); msl.addLast(33); msl.addLast(44); msl.display(); msl.remove(11); msl.remove(33); msl.display();结果
删除所有val值
定义cur是遍历节点，pre是cur的前驱节点
如果cur的值为val，
- pre.next=cur.next
- cur=pre.next
否则，
- pre=cur
- cur=cur.next
注意
- 处理空链表：判断head为空后，直接return
- 处理头节点是要删的节点：head=head.next，使用while循环防止前面都是要删的节点情况;
//删除所有val值 public void removeAllVal(int val){ if(head==null){ return; } //删头节点 while(head.val==val) { head = head.next; } ListNode pre=head; ListNode cur=head.next; while(cur!=null){ if(cur.val==val){ pre.next=cur.next; }else{ pre=cur; } cur=cur.next; } }测试
msl.addFirst(4); msl.addFirst(4); msl.addFirst(3); msl.addFirst(2); msl.addFirst(4); msl.addFirst(1); msl.display(); msl.removeAllVal(4); msl.display();结果
清空链表
//清空链表 public void clear(){ //法1 // head=null; //法2 遍历，将每个节点都置为空 ListNode cur=head; while(cur!=null){ ListNode curN=cur.next; // cur.val=null;//如果是引用类型就置为null cur.next=null; cur=curN; } head=null; }