首先来构造数据结构，这里单链表的节点类是以内部类的形式出现
数据结构
节点类：
节点类中应该有数据域和指针域
/**
* 节点类
*/
class Entry {
//数据域
private int data;
//指针域
private Entry next;
//无参构造函数
public Entry() {
this(0,null);
}
//有参构造函数
public Entry(int data, Entry next) {
this.data = data;
this.next = next;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Entry getNext() {
return next;
}
public void setNext(Entry next) {
this.next = next;
}
}
单链表类
来写外部类，外部类就是单链表类，单链表类需要维护一个头结点，头结点的数据域是不存放数据的，头结点的指针域为空。
public class MiNiLinkedList {
//头结点
private Entry head;
public MiNiLinkedList() {
this.head = new Entry(0,null);
}
}
注意，节点类是单链表类的一个内部类
操作
头插法
插入节点是从头开始插入，思路很简单，直接把生成的新节点插入到头节点的后面，注意不能丢失原来头结点后面的节点，所以需要先把原来的节点链到新节点的后面，再把新节点接到头结点的后面。
时间复杂度：O（1）
//从头插入节点
public void insertHead(int data) {
//new一个新节点
Entry entry = new Entry(data, null);
//防止后面的节点丢失，先把后面的节点接到新节点的后面
entry.next = head.getNext();
//把新节点接入到头结点的后面
head.next = entry;
}
尾插法
从链表的末尾插入元素，首先需要定义一个指针插入到链表的末尾，然后把新生成的节点插入到末尾的后面。
由于需要遍历到链表的后面，所以时间复杂度是O（n）
//从尾进行插入
public void insertTail(int data) {
//new一个新的节点
Entry entry = new Entry(data, null);
//定义一个指针,遍历到链表的最后
Entry last = head;
while(last.next != null) {
last = last.next;
}
last.next = entry;
}
有时经常进行尾插操作时，为了不用每次插入都遍历到链表的最后，可以维护一个尾节点，如果维护尾结点需要注意几点：
- 在第一次头插的时候，需要移动尾结点到新节点
- 每一次尾插的时候都需要更新尾结点
- 在删除的时候，如果删除的节点是尾结点，那么需要把尾结点往前移动
删除第一个值为data的节点
定义一个指针指向前一个节点，遍历链表，当下一个节点是要找的节点的时候，通过当前节点删除该节点。
//删除第一个值为data的节点
public boolean removeFirst(int data) {
//定义一个指针，找到待删除节点的前一个节点
Entry entry = head;
while(entry.next!=null && entry.next.data!=data){
entry = entry.next;
}
//删除待删节点
if(entry.next == null) {
//遍历到最后
return false;
} else {
//删除该节点
entry.next = entry.next.next;
return true;
}
}
可以看到我的代码实现是维护了一个指针，其实也可以维护两个指针，移动的时候两个指针同时移动，这样理解起来比较容易。
删除所有值为data的节点
刚才删除第一个值为data的节点是遍历到对应的位置，指针就停下来，而删除所有值为data的节点，在遍历的过程中是不停止的，如果找到了值为data的节点，就删除该节点，然后继续往下遍历。
//删除所有值为data的节点
public void removeAll(int data) {
//定义一个指针，找到待删除节点的前一个节点
Entry entry = head;
while(entry.next!=null){
if(entry.next.data == data) {
entry.next = entry.next.next;
} else {
entry = entry.next;
}
}
}
查询
查询的逻辑比较简单，遍历整个链表即可
public boolean query(int data) {
//定义一个指针
Entry cur = head.next;
//逐一遍历
while(cur != null) {
if(cur.data == data) {
return true;
}
cur = cur.next;
}
return false;
}
在讲解完了单向链表了以后，单向循环链表就非常简单了，单向循环链表的特点是最后一个节点的指针域为head，所以在一些判断的过程中就需要把null该为head就可以了。一起来看看有什么变化
节点类的数据结构是相同的，直接来看循环链表的数据结构
数据结构
循环链表的数据结构我们在初始化头结点head的时候，需要让head的指针域指向自己，成为一个自己和自己的环
public class CircleLinkedList {
//头结点
private Entry head;
public CircleLinkedList() {
this.head = new Entry(0,null);
head.next = head;
}
}
头插
由于在构造函数中头结点已经自己指向了自己，插入不会涉及尾到头这一层关系的变动，所以头插的代码是完全不用变化的。
//从头插入节点
public void insertHead(int data) {
//new一个新节点
Entry entry = new Entry(data, null);
//防止后面的节点丢失，先把后面的节点接到新节点的后面
entry.next = head.getNext();
//把新节点接入到头结点的后面
head.next = entry;
}
尾插
尾插在单向链表中需要找到尾结点，我们刚才说过了尾结点的标志不是null，是head，看一下代码的改动
//从尾进行插入
public void insertTail(int data) {
//1.第一处改动，新创建的节点指向头结点
Entry entry = new Entry(data, head);
Entry last = head;
//2.第二处改动，结束的标志不是null，而是head
while(last.next != head) {
last = last.next;
}
last.next = entry;
}
这些想不来的话画画图是很好理解的
删除第一个值为data的节点
直接改掉null为head即可
//删除第一个值为data的节点
public boolean removeFirst(int data) {
//定义一个指针，找到待删除节点的前一个节点
Entry entry = head;
while(entry.next!=head && entry.next.data!=data){
entry = entry.next;
}
//删除待删节点
if(entry.next == head) {
//遍历到最后
return false;
} else {
//删除该节点
entry.next = entry.next.next;
return true;
}
}
删除所有值为data的节点
同样，改掉null
//删除所有值为data的节点
public void removeAll(int data) {
//定义一个指针，找到待删除节点的前一个节点
Entry entry = head;
while(entry.next!=head){
if(entry.next.data == data) {
entry.next = entry.next.next;
} else {
entry = entry.next;
}
}
}
查询
改null为head
public boolean query(int data) {
//定义一个指针
Entry cur = head.next;
//逐一遍历
while(cur != head) {
if(cur.data == data) {
return true;
}
cur = cur.next;
}
return false;
}
到这，单向循环链表就创建完了，可以自行测试一下