一.单链表
链表是一种在物理存储结构上非连续的存储结构，数据元素的逻辑顺序通过链表中的引用链接次序实现。链表的结构多样，我们通过实现无头单向非循环链表，来进一步理解链表。
从图中可以看出，链表在逻辑上是连续的，但在物理存储结构上不一定是连续的
由于链表是单向的，可以通过前一个节点访问后一个节点，不能通过后一个节点访问前一个结点
二.单链表基本操作的实现
1.单链表类、属性的定义
要创建链表首先要有节点，我们可以将节点定义为内部类
public class MySingleList{ static class ListNode{ //存放当前结点的值 private int val; //存放下一节点的地址 private ListNode next; public ListNode(){} public ListNode(int val){ this.val = val; } } }
由于链表是通过前一个节点访问下一个节点的，因此我们需要知道链表的第一个节点，因此我们需要定义一个头节点
private ListNode head;//第一个节点
2.求链表长度
定义变量count用以计算，遍历链表，统计链表节点个数
//求链表长度 public int size() { int count = 0; //定义节点cur，用于遍历链表 ListNode cur = head; while(cur != null){ count++; //指向下一节点 cur = cur.next; } return count; }
3.链表是否包含值为key的节点
遍历链表，判断节点的值是否等于key
public boolean contains(int key) { ListNode cur = head; while(cur != null){ if(cur.val == key){ return true; } cur = cur.next; } return false; }
4.添加元素
链表添加元素的方式通常有三种，头插、尾插和在指定位置添加元素。
头插：在链表的第一个节点前插入元素
实现头插，就是让要插入的节点node指向原本链表的头节点head，再更新链表的第一个节点，让head指向新插入的节点
//头插 public void addFirst(int data) { //创建新节点 ListNode listNode = new ListNode(data); listNode.next = head; head = listNode; }
尾插：在链表的最后插入元素
实现尾插，首先要找到链表的最后一个节点，再将最后一个节点的next更新为新节点即可
//尾插 public void addLast(int data) { ListNode newNode = new ListNode(data); //若链表为空，直接将head更新为插入节点 if(head == null){ head = newNode; }else{ //通过遍历找到最后一个节点 ListNode cur = head; while(cur.next != null){ cur = cur.next; } cur.next = newNode; } }
在指定位置添加元素
在指定位置添加元素，首先要判断指定位置index是否合法，若index < 0 或 index > size，则不能添加元素，然后通过遍历找到节点插入的位置，由于链表为单链表，不能通过后一节点找到前一节点，因此，我们需要找到插入位置的前驱节点，然后通过前驱节点实现链表在index位置的插入
//在任意位置添加元素 public void addIndex(int index, int data) { //index不正确，无法添加元素 if(index < 0 || index > size()){ throw new RuntimeException("输入位置不正确，无法添加元素！"); }else if(index == 0){//在0位置插入，即为头插 addFirst(data); }else{ ListNode cur = head;//用cur遍历链表，找到前驱节点 ListNode listNode = new ListNode(data); int count = 0; while(count != index-1){ count++; cur = cur.next; } //添加元素 listNode.next = cur.next; cur.next = listNode; } }
5.删除节点
删除第一个值为key的节点：与在指定位置添加元素相同，我们需要找到第一个值为key的节点node的前驱节点，然后才能删除值为key的节点。由于JVM会将未被任何引用指向的对象回收掉，我们只需让node的前驱节点指向node的下一节点，即可实现删除
//删除第一个值为key的节点 public boolean remove(int key) { ListNode cur = head; //链表第一个节点的值即为key，头删 if(head.val == key){ head = head.next; return true; }//通过遍历找到第一个值为key的节点的前驱节点 while(cur.next != null){ if(cur.next.val == key){//找到了，删除节点 cur.next = cur.next.next; return true; } cur = cur.next; } return false;//未找到值未key的节点，返回false }
删除所有值为key的节点：首先要找到值为key的节点node，将node的上一节点指向node的下一节点，即可删除值为key的节点，注意考虑头节点值为key的情况，要删除链表中所有值为key的节点，利用while循环即可实现。
//删除所有值为key的节点 public void removeAllKey(int key) { //若链表为空，则直接返回null if(head == null){ return; } ListNode cur = head; while(cur.next != null){ if(cur.next.val == key){ cur.next = cur.next.next; }else{ cur = cur.next; } } //单独考虑头节点的值是否等于val if(head.val == key){ head = head.next; } }
6.清空链表
由于JVM会将未被任何引用指向的对象回收掉，清空链表可以将每个节点的指向都置为null，即切断节点之间的链接，也可以直接将head置为null
将每个节点的指向都置为null
//清空链表 public void clear() { if(head == null){//链表本身为空 return; } ListNode cur = head; while(cur != null){ ListNode next = cur.next;//记录下一节点 cur.next = null; cur = next; } }
直接将head置为null
//清空链表 public void clear() { head = null; }
三、完整代码
public class MySingleList { static class ListNode{ //存放当前结点的值 private int val; //存放下一节点的地址 private ListNode next; public ListNode(){} public ListNode(int val){ this.val = val; } } private ListNode head;//第一个节点 //求链表长度 public int size() { int count = 0; //定义节点cur，用于遍历链表 ListNode cur = head; while(cur != null){ count++; //指向下一节点 cur = cur.next; } return count; } //链表是否包含值为key的节点 public boolean contains(int key) { ListNode cur = head; while(cur != null){ if(cur.val == key){ return true; } cur = cur.next; } return false; } //头插 public void addFirst(int data) { //创建新节点 ListNode listNode = new ListNode(data); listNode.next = head; head = listNode; } //尾插 public void addLast(int data) { ListNode newNode = new ListNode(data); //若链表为空，直接将head更新为插入节点 if(head == null){ head = newNode; }else{ //通过遍历找到最后一个节点 ListNode cur = head; while(cur.next != null){ cur = cur.next; } cur.next = newNode; } } //在任意位置添加元素 public void addIndex(int index, int data) { //index不正确，无法添加元素 if(index < 0 || index > size()){ throw new RuntimeException("输入位置不正确，无法添加元素！"); }else if(index == 0){//在0位置插入，即为头插 addFirst(data); }else{ ListNode cur = head;//用cur遍历链表，找到前驱节点 ListNode listNode = new ListNode(data); int count = 0; while(count != index-1){ count++; cur = cur.next; } //添加元素 listNode.next = cur.next; cur.next = listNode; } } //删除第一个值为key的节点 public boolean remove(int key) { ListNode cur = head; //链表第一个节点的值即为key，头删 if(head.val == key){ head = head.next; return true; }//通过遍历找到第一个值为key的节点的前驱节点 while(cur.next != null){ if(cur.next.val == key){//找到了，删除节点 cur.next = cur.next.next; return true; } cur = cur.next; } return false;//未找到值未key的节点，返回false } //删除所有值为key的节点 public void removeAllKey(int key) { //若链表为空，则直接返回null if(head == null){ return; } ListNode cur = head; while(cur.next != null){ if(cur.next.val == key){ cur.next = cur.next.next; }else{ cur = cur.next; } } //单独考虑头节点的值是否等于val if(head.val == key){ head = head.next; } } //清空链表 public void clear() { if(head == null){//链表本身为空 return; } ListNode cur = head; while(cur != null){ ListNode next = cur.next;//记录下一节点 cur.next = null; cur = next; } //或直接将head置为null //head = null; } }
