一：单链表的概念：
单链表是一种在内存上不连续，而逻辑上连续的一种线性表。
单链表是由若干个节点和头节点组成的数据结构；
每个节点又分为数值域和next域:
数值域用来存储数据；
next域用来存储下一个节点的地址；
下图就是一个节点：
链表由若干个节点组成：
二：单链表中的方法：
// 1、无头单向非循环链表实现 public interface IList { //头插法 public void addFirst(int data); //尾插法 public void addLast(int data); //任意位置插入,第一个数据节点为0号下标 public void addIndex(int index,int data); //查找是否包含关键字key是否在单链表当中 public boolean contains(int key); //删除第一次出现关键字为key的节点 public void remove(int key); //删除所有值为key的节点 public void removeAllKey(int key); //得到单链表的长度 public int size(); //打印单链表 public void display(); //清空单链表 public void clear(); }
我们将模拟实现这些方法。
1：得到单链表的长度
public int size();
模拟实现:
定义一个变量count，用来计数；
这里我们采取遍历头结点的方法来获取长度：
当头节点不为空的时候，我们就让count++；
public int size() { ListNode cur=head; int count=0; while(cur!=null){ count++; cur=cur.next;//cur指向下一个节点 } return count; }
2：查找是否包含关键字key是否在单链表当中
public boolean contains(int key);
总体思路还是遍历链表节点中的数据，如果找到了返回true;如果链表遍历完了,仍没有找到，返回false。
public boolean contains(int key) { ListNode cur=head; while(cur!=null){ if(cur.val==key){ return true; } cur=cur.next; } return false; }
可能有人会想到：如果单链表为空呢？
上面的代码也是没问题的，因为单链表为空，不会进入循环，会返回false的。
3：打印单链表中的数据：display（）
@Override public void display() { ListNode cur=head; while(cur!=null){ System.out.print(cur.val+" "); cur=cur.next; } System.out.println(); }
3： 头插法
将一个节点放在头结点的位置：
头插：在这里我们只需要将node指向他的下一个节点，然后再让头节点更新数据：
看到上图：可能有小伙伴和我有一样的疑问，为什么插入数据的时候，要先绑定后面的数据呢？
这是因为
head=node; node.next=head;
具体代码实现：
当先更新head的指向时，这时，还没有修改node 的指向，那么原来head指向的节点就没有被指向了，这是它就会被回收！
public void addFirst(int data) { ListNode node =new ListNode(data);//实例化一个单链表 if(head==null){ head=node;//如果单链表为空,插入的节点就是头结点 }else{ //node节点的next指向head; node.next=head; head=node;//node变成头节点 } }
测试一下：
public class Test { public static void main(String[] args) { SingleLinkedList singleLinkedList=new SingleLinkedList(); singleLinkedList.addFirst(1); singleLinkedList.addFirst(2); singleLinkedList.addFirst(3); singleLinkedList.addFirst(4); singleLinkedList.display(); } }
4：尾插法
在这里我们将最后一个节点的next域指向node即可！
head是指向头结点的，那么我们如何获得最后一个节点，进而修改它的next域呢？
很简单，我们看最后一个节点的特点：它的next域为null；那么我们只需要让cur节点从头结点往后移动，当cur.next==null时，说明cur节点指向最后一个节点
public void addLast(int data) { ListNode node =new ListNode(data); if(head==null){ head=node; }else { ListNode cur = head; while (cur.next != null) { cur = cur.next; } //此时cur指向最后一个节点 cur.next = node; } }
测试一下：
public class Test{ public static void main(String[] args) { SingleLinkedList singleLinkedList=new SingleLinkedList(); singleLinkedList.addLast(1); singleLinkedList.addLast(2); singleLinkedList.addLast(3); singleLinkedList.addLast(4); singleLinkedList.display(); } }
5：任意位置插入：
在任意位置插入：我们首先要判断插入的位置是否有效；
然后判断单链表是否为空；
在根据插入的位置：
(1)index=0:往第一个节点也就是0下标的位置插入数据，也就是头插法；
(2)index=size()：往最后一个位置插入数据，也就是尾插法
（3）其他情况下：
index就是插入中间数据：因为要修改节点的指向，我们需要让index的前一个位置（cur）的next域指向index节点，让index处的节点指向cur的下一个节点
代码实现：
public void addIndex(int index, int data) { if(index<0||index>size()){//判断index是否有效 throw new IndexException("index越界"+index); } ListNode node =new ListNode(data); if(head == null) {//判断链表是否为空 head = node; return; } if(index==0){ //头插 addFirst(data); return; } if(index==size()){ //尾插 addLast(data); return; } //中间插入 ListNode cur=searchPrevIndex(index);//cur指向index下标的前一个节点 ListNode curNext=cur.next; cur.next=node; node.next=curNext; } private ListNode searchPrevIndex(int index) { ListNode cur=head; int count=0; while(count!=index-1){ count++; cur=cur.next; } return cur; } @Override public boolean contains(int key) { ListNode cur=head; while(cur!=null){ if(cur.val==key){ return true; } cur=cur.next; } return false; }
测试一下：
public class Test{ public static void main(String[] args) { SingleLinkedList singleLinkedList=new SingleLinkedList(); singleLinkedList.addLast(1); singleLinkedList.addLast(2); singleLinkedList.addLast(3); singleLinkedList.addLast(4); singleLinkedList.display(); System.out.println("==========================="); singleLinkedList.addIndex(0,10); singleLinkedList.display(); System.out.println("================="); singleLinkedList.addIndex(4,22); singleLinkedList.display(); System.out.println("================="); singleLinkedList.addIndex(1,100); singleLinkedList.display(); } }
6：删除第一次出现关键字为key的节点
在这里定义一个cur指针用来表示要删除节点的头节点，
public void remove(int key) { if(head==null){ return; } if(head.val==key){ head=head.next; return; } ListNode cur=searchPrevRemove(key); if(cur==null){ return; } ListNode del=cur.next; cur.next=del.next; } private ListNode searchPrevRemove(int key){ ListNode cur=head; while(cur.next!=null){ if(cur.next.val==key){ return cur; } cur=cur.next; } return null; } @Override public void removeAllKey(int key) { } @Override public int size() { ListNode cur=head; int count=0; while(cur!=null){ count++; cur=cur.next;//cur指向下一个节点 } return count; } @Override public void display() { ListNode cur=head; while(cur!=null){ System.out.print(cur.val+" "); cur=cur.next; } System.out.println(); } @Override public void clear() { } }
测试一下：
public class Test{ public static void main(String[] args) { SingleLinkedList singleLinkedList=new SingleLinkedList(); singleLinkedList.addLast(1); singleLinkedList.addLast(2); singleLinkedList.addLast(3); singleLinkedList.addLast(4); singleLinkedList.addLast(5); singleLinkedList.display(); singleLinkedList.remove(1); singleLinkedList.display(); System.out.println("============="); singleLinkedList.remove(5); singleLinkedList.display(); System.out.println("==============="); singleLinkedList.remove(3); singleLinkedList.display(); } }
6：删除所有值为key的节点
定义两个指针：
prev表示可能要删除节点的前一个节点
cur表示要删除的节点。
我们在这里从第二个节点开始遍历，如果cur是要删除的节点，让prev.next=cur.next,也就是让prev指向下一个节点，prev是可能要删除的节点的前一个节点，当cur被删除后，prev仍然是cur下一个节点的前一个节点，所以cur被删除后，prev不能移动。
如果cur节点没有被删除，说明cur不是要被删除的节点，prev要移动到这个cur节点。
为什么此时prev移动呢？
cur节点没有被删除，说明可能删除节点的前一个节点就是cur节点了；判断cur移动到的下一个节点是否要被删除，prev表示可能要删除节点的前一个节点，所以当cur不被删除时，prev要移动
public void removeAllKey(int key) { if(head==null){ return;//单链表为空，直接返回 } ListNode cur=head.next;//从第二个节点判断是否等于key ListNode prev=head; while(cur!=null){ if(cur.val==key){ prev.next=cur.next; cur=cur.next; }else{ prev=cur; cur=cur.next; } } if(head.val==key){//判断头节点是否==key head=head.next; } }
测试一下：
public class Test{ public static void main(String[] args) { SingleLinkedList singleLinkedList=new SingleLinkedList(); singleLinkedList.addLast(1); singleLinkedList.addLast(2); singleLinkedList.addLast(6); singleLinkedList.addLast(3); singleLinkedList.addLast(4); singleLinkedList.addLast(5); singleLinkedList.addLast(6); singleLinkedList.display(); System.out.println("=========================="); singleLinkedList.removeAllKey(6); singleLinkedList.display(); } }
