图解顺序表+单链表-1
https://developer.aliyun.com/article/1503982
二 图解单链表
概念
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
链表的分类
单向带头循环 单向带头不循环
单向不带头循环 单向不带头不循环
双向带头循环 双向带头不循环
双向不带头循环 双向不带头不循环
对于单链表而言，我们主要着重于单向不带头不循环。
节点
对于单链表而言，不是利用数组来描述，我们用节点来描述链表，对于节点是由两部分组成的val(一个值，为整型)和next（引用类型，用来指向下一个地址）组成的具体如图表示：
头结点与尾节点
在单链表中，我们会将第一个作为头节点，注意在单向不带头不循环链表中这个头结点是可以变的（头结点也就意味着是单链表的第一位），对于尾节点的next是null，例子如图：
单链表常用实现方法
1 抽象类
对于节点是一种类，里面会包含val以及next两者成员属性。
单链表是一种类，里面会包含节点，以及对单链表进行操作的基本实现方法
class nodelist{//节点 public int val; public nodelist next; public nodelist(int val){ this.val=val; } } class singlelist{//单链表 nodelist head; }
2 在单链表中进行实现方法
2.1 实例化一个单链表
代码实现：
public void creat(){ nodelist list=new nodelist(10); nodelist list1=new nodelist(20); nodelist list2=new nodelist(35); nodelist list3=new nodelist(20); nodelist list4=new nodelist(23); list.next=list1; list1.next=list2; list2.next=list3; list3.next=list4; head=list; }
2.2 遍历单链表
利用循环进行遍历，代码实现如下
//对单链表打印 public void display(){ nodelist cur=head;//由于头结点没有改变，所以不能移动，此时创建一个等于head的头结点，代替head进行遍历 while (cur!=null){ System.out.print(cur.val+" "); cur=cur.next;//此时cur就往后移动 } }
2.3 头插法
//头插法 public void addFirst(int data){ nodelist first=new nodelist(data); first.next=head; head=first; }
2.4 尾插法
//尾插法 public void addLast(int data){ nodelist last=new nodelist(data); nodelist cur=head; while (cur.next!=null){ cur=cur.next; } cur.next=last;//到达尾节点之后，把null换成last的地址 }
2.5查找是否包含关键字key是否在单链表当中
对于这个，我们可以采用遍历单链表，查找是否会有于key相等的值。
//查找是否包含关键字key是否在单链表当中 public boolean contains(int key){ if (head==null){//单链表为空 return false; } nodelist cur=head; while (cur!=null){ if(cur.val==key){ return true; } cur=cur.next; } return false; }
2.6 求单链表的长度
//得到单链表的长度 public int size(){ if (head==null){ return -1;//表示单链表为空的情况 } int count=0; nodelist cur=head; while (cur!=null){ count++; cur=cur.next; } return count; }
2.7删除第一次出现关键字为key的节点
public void remove(int key){ boolean ret=contains(key); if (ret==false){//判断单链表是否包含你要找的元素，调用contains（key） System.out.println("没有你要删除的数据"); return; } if (head.val==key){//但删除的是头结点时 head=head.next; return; } nodelist cur=head; while (cur!=null){ if (cur.next.val==key){ cur.next=cur.next.next; return; }else{ cur=cur.next; } } }
2.8删除所有值为key的节点
//删除所有值为key的节点 public void removeAllKey(int key){ boolean ret=contains(key);//判断是否含有要删除的关键字key if (ret==false){ System.out.println("没有你要删除的元素"); return; } nodelist cur=head; nodelist prve=head.next; while (prve!=null){ if (prve.val==key){ cur.next=prve.next; prve=prve.next; }else{ cur=cur.next; prve=prve.next; } } if (head.val==key){//如果头结点也是等于key head=head.next; } }
2.9任意位置插入,第一个数据节点为0号下标
插入前：
插入后：
//任意位置插入,第一个数据节点为0号下标 public void addIndex(int index,int data){ nodelist add=new nodelist(data); if (index==0){//头插法 addFirst(data); return; } if (index==size()){//尾插法 addLast(data); return; } nodelist cur =head; while (index-1!=0){ cur=cur.next; } add.next=cur.next; cur.next=add; }
2.10清空单链表
public void clear(){ //暴力清空 head=null; while (head!=null){ nodelist cur=head.next; head=null; head=cur; } }
顺序表与单链表总结：
对于顺序表与单链表我们应该要懂得操作的原理是什么，如何进行操作，可以通过画图来理解，从而加深自己对于单链表与顺序表的理解与应用，之后就可以通过一些练习来巩固，发散自己的思维，从而提升自我的编程能力，具体的题目，可以看一下我之后的刷题文章记录。
