一、链表是什么
链表不是一整块内存，它把每一份数据包装成节点Node。
每个节点做两件事：存真正的数据 data ；存下一个节点的地址 next ，指向下一个小伙伴
1.链表的优点
- 新增尾部数据很快。我们代码里加了尾节点 last ，直接让last.next指向新节点就行，不用循环找尾巴，速度很快。
- 不需要提前定容量。数组要一开始就写有多大，链表想存多少就存多少，节点随时new出来。
- 删除、插入的时候，不需要像数组一样把大量元素往后/往前挪。只需要改几个next的指向。
2.链表的缺点
4. 不能随机访问！想拿第index位置的数据，必须从头head一个一个往后遍历，不能直接一下拿到。所以 get(index) 方法要写for循环。
5. 查询慢，找数据只能从头挨个找。
6. 需要额外的内存存next引用。
//链表的三个变量publicNodehead;publicNodelast;publicintsize=0;节点类Node
classNode{publicintdata;//数据本身publicNodenext;//保存下一个节点的变量//构造方法publicNode(intdata){this.data=data;}publicNode(){}二、链表的实现步骤
我们要实现的功能分别是：尾插add、指定位置插入insert、按下标删除remove、按数值删除第一个removes、删除全部相同数据removeAll。
1.实现尾部添加 add(int data)
//添加publicvoidadd(intdata){//创建节点保存数据Nodenode=newNode(data);//定义变量单独保存头节点Nodecurr=head;if(curr==null){//把node保存为头节点head=node;last=node;}else{//循环遍历到尾节点//尾节点添加数据last.next=node;last=node;}size++;}2.指定下标插入 insert(int index,int data)
//插入:遍历到index位置的上一个节点publicvoidinsert(intindex,intdata){//判断是否越界if(index<0||index>=size){System.out.println("index 越界...");return;}Nodenode=newNode(data);Nodecurr=head;//插在表头if(index==0){node.next=head;head=node;if(last==null){last=node;}}elseif(index==size){//插在末尾last.next=node;last=node;}else{//插在中间for(inti=0;i<index-1;i++){curr=curr.next;}node.next=curr.next;curr.next=node;}size++;}***3.按下标删除remove(int index) ***
//删除指定位置数据publicintremove(intindex){if(index<0||index>=size){System.out.println("index 越界...");return-1;}intolddata;Nodecurr=head;//删头节点if(index==0){olddata=head.data;//存储被删的数据head=head.next;//头指针后移//如果链表空了尾指针也置空if(head==null){last=null;}size--;returnolddata;}//删中间或尾节点for(inti=0;i<index-1;i++){curr=curr.next;}Nodednode=curr.next;olddata=dnode.data;curr.next=dnode.next;//直接跳过被删节点if(dnode==last){last=curr;}size--;returnolddata;}4.按数值删除第一个removes(int data)
//删除指定数据publicbooleanremoves(intdata){Nodecurr=head;if(head==null){returnfalse;}//数据在头节点if(head.data==data){head=head.next;size--;if(head==null){last=null;}returntrue;}while(curr.next!=null){if(curr.next.data==data){Nodednode=curr.next;curr.next=dnode.next;if(dnode==last){last=curr;}size--;returntrue;}curr=curr.next;}returnfalse;}5.删除全部相同数据removeAll(int data)
//删除所有相同数据publicbooleanremoveAll(intdata){Nodecurr=head;if(head==null){returnfalse;}//头节点while(head!=null&&head.data==data){head=head.next;size--;if(head==null){last=null;}returntrue;}//在中间while(curr.next!=null){if(curr.next.data==data){Nodednode=curr.next;curr.next=dnode.next;if(dnode==last){last=curr;}size--;}else{//没找到相同数据才往后走curr=curr.next;}}returnfalse;}6.get获取元素、size获取长度
链表不能随机访问，get只能循环走到对应下标：
//获取publicintget(intindex){if(index<0||index>=size){System.out.println("index 越界...");return-1;}//利用循环遍历到index位置Nodecurr=head;for(inti=0;i<index;i++){curr=curr.next;}returncurr.data;}//长度publicintsize(){returnsize;}
