大家好，又见面了，我是你们的朋友全栈君。
Java内部也有自己的链表–LinkedList，但是我们今天不是讨论LinkedList，而是自己来实现一个单链表，包括简单的增删查改：
- 单链表的结构
- 单链表的基本操作
- 虚拟头结点的使用
整个类的设计如下：
public class Linked <T>{
private class Node{
private T t;
private Node next;
public Node(T t,Node next){
this.t = t;
this.next = next;
}
public Node(T t){
this(t,null);
}
}
private Node head; //头结点
private int size; //链表元素个数
//构造函数
public Linked(){
this.head = null;
this.size = 0;
}
}
单链表的结构
一种链式存取的数据结构，单链表中的数据是以结点的形式存在，每一个结点是由数据元素和下一个结点的存储的位置组成。单链表与数组相比的最大差别是：单链表的数据元素存放在内存空间的地址是不连续的，而数组的数据元素存放的地址在内存空间中是连续的，这也是为什么根据索引无法像数组那样直接就能查询到数据元素。
[单链表结构图]![Java基础--单链表的实现[通俗易懂]](http://javaforall.cn/synimg/402e668f-df01-4990-889a-fd5331f3d1c12022042850c5109c-d6a7-4236-a1a7-90016c4263f81.jpg)
链表存储的结点
private class Node{
private T t;
private Node next;
public Node(T t,Node next){
this.t = t;
this.next = next;
}
public Node(T t){
this(t,null);
}
}
链表的基本操作
包括链表的增删查改，以及判别某结点是否存在链表中
链表结点的增加
进行结点的添加的时候，是根据索引来进行操作的，由于成员变量size记录了当前链表的元素个数，进行某个索引位置的结点插入就会很方便了。先找到该目标索引的前一个结点，记录为pre，把要插入的结点node的下一个结点node.next指向pre的下一个结点pre.next；再把pre.next指向node结点。如果先进行pre.next指向要插入的结点，再进行node.next指向pre.next的话，无疑是要插入的结点自己指向了自己，无法连接上整个链表，在链表的操作中，有时候顺序的执行会带来不一样的结果。
//链表头部添加元素
public void addFirst(T t){
Node node = new Node(t); //节点对象
node.next = this.head;
this.head = node;
//this.head = new Node(e,head);等价上述代码
this.size++;
}
//向链表尾部插入元素
public void addLast(T t){
this.add(t, this.size);
}
//向链表中间插入元素
public void add(T t,int index){
if (index <0 || index >size){
throw new IllegalArgumentException("index is error");
}
if (index == 0){
this.addFirst(t);
return;
}
Node preNode = this.head;
//找到要插入节点的前一个节点
for(int i = 0; i < index-1; i++){
preNode = preNode.next;
}
Node node = new Node(t);
//要插入的节点的下一个节点指向preNode节点的下一个节点
node.next = preNode.next;
//preNode的下一个节点指向要插入节点node
preNode.next = node;
this.size++;
}
链表结点的删除
//删除链表元素
public void remove(T t){
if(head == null){
System.out.println("无元素可删除");
return;
}
//要删除的元素与头结点的元素相同
while(head != null && head.t.equals(t)){
head = head.next;
this.size--;
}
/**
* 上面已经对头节点判别是否要进行删除
* 所以要对头结点的下一个结点进行判别
*/
Node cur = this.head;
while(cur != null && cur.next != null){
if(cur.next.t.equals(t)){
this.size--;
cur.next = cur.next.next;
}
else cur = cur.next;
}
}
在进行链表的结点删除时候，要分情况讨论：
当要删除的结点位于头结点的时候：
如下图要删除的元素1的结点位于头结点，先进行while判断头结点是否为null且判断该结点的元素是否为要删除的元素，如果是把head指向head.next即可，直接跳过头结点，直到头结点不是要删除的元素就结束循环。
[要删除的元素1位于头结点]![Java基础--单链表的实现[通俗易懂]](http://javaforall.cn/synimg/db9a38c1-ce67-4f73-b37f-e7ec2ef36b46202204286a8f18b3-924e-4636-89b9-5ce4f4f8caca1.jpg)
当要删除的结点不在头结点的时候：如下图删除元素为3的结点，由于上面已经判断了头结点不是要删除的元素，所以我们从头结点的下一个结点开始循环，即cur.next，当cur.next是要被删除的元素时，直接cur.next = curr.next.next就能直接跳过cur.next，断开。
[要删除结点的元素为3的结点]
![Java基础--单链表的实现[通俗易懂]](https://javaforall.cn/wp-content/plugins/wp-fastest-cache-premium/pro/images/blank.gif)
删除链表的头结点的元素和删除链表的尾结点的元素
//删除链表第一个元素
public T removeFirst(){
if(this.head == null){
System.out.println("无元素可删除");
return null;
}
Node delNode = this.head;
this.head = this.head.next;
delNode.next =null;
this.size--;
return delNode.t;
}
//删除链表的最后一个元素
public T removeLast(){
if(this.head == null){
System.out.println("无元素可删除");
return null;
}
//只有一个元素
if(this.getSize() == 1){
return this.removeFirst();
}
Node cur = this.head; //记录当前结点
Node pre = this.head; //记录要删除结点的前一个结点
while(cur.next != null){
pre = cur;
cur = cur.next;
}
pre.next = cur.next;
this.size--;
return cur.t;
}
经过上面在进行链表的结点删除的时候，会发现在删除的过程中很麻烦，还得考虑头结点（因为我们在删除结点的时候，都是先找到待删除结点del的前一个结点pre，然后直接进行跳过操作，即pre.next = pre.next.next，但是删除结点头结点的时候就无法操作），给我们添加了麻烦，为此我们可以给链表添加一个虚拟的头结点，说白了就是重新new一个结点对象，该结点对象的下一个结点指向了我们之前的头结点，让我们在删除结点的时候，无须再考虑之前的头结点了！
虚拟头结点删除链表元素的实现
//加入虚拟头结点的链表进行删除
public void removeElt(T t){
//构造虚拟头结点，并且下一个结点指向head
Node dummy = new Node(t,this.head);
//声明结点指向虚拟头结点
Node cur = dummy;
//从虚拟头结点的下一个结点开始遍历
while(cur.next != null){
if(cur.next.t.equals(t)){
cur.next = cur.next.next;
this.size--;
}
else cur = cur.next;
}
//去除虚拟头结点
this.head = dummy.next;
}
使用虚拟头结点进行链表的插入
刚开始那部分的结点添加是基于索引的情况实现，当我们无法知道一个结点的位于链表的哪个位置时候，只知道要插入在某个元素的前面，下面的代码基于上述情况实现。
/**
*
* @param t:插入在t元素的位置
* @param des：要插入的元素
*/
public void insert(T t,T des){
//构造虚拟头结点，并且下一个结点指向head
Node dummy = new Node(null,this.head);
//构造要插入的结点
Node dNode = new Node(des);
//声明变量cur指向虚拟头结点
Node cur = dummy;
while(cur.next != null){
if(cur.next.t.equals(t)){
dNode.next = cur.next;
cur.next = dNode;
this.size++;
break;
}
else cur = cur.next;
}
this.head = dummy.next;
}
查找某个元素是否在链表的结点上
//链表中是否包含某个元素
public boolean contains(T t){
Node cur = this.head;
while(cur != null){
if(cur.t.equals(t)){
return true;
}
else cur = cur.next;
}
return false;
}
完整的代码实现：
package LinkedList;
public class Linked <T>{
private class Node{
private T t;
private Node next;
public Node(T t,Node next){
this.t = t;
this.next = next;
}
public Node(T t){
this(t,null);
}
}
private Node head; //头结点
private int size; //链表元素个数
//构造函数
public Linked(){
this.head = null;
this.size = 0;
}
//获取链表元素的个数
public int getSize(){
return this.size;
}
//判断链表是否为空
public boolean isEmpty(){
return this.size == 0;
}
//链表头部添加元素
public void addFirst(T t){
Node node = new Node(t); //节点对象
node.next = this.head;
this.head = node;
// this.head = new Node(e,head);等价上述代码
this.size++;
}
//向链表尾部插入元素
public void addLast(T t){
this.add(t, this.size);
}
//向链表中间插入元素
public void add(T t,int index){
if (index <0 || index >size){
throw new IllegalArgumentException("index is error");
}
if (index == 0){
this.addFirst(t);
return;
}
Node preNode = this.head;
//找到要插入节点的前一个节点
for(int i = 0; i < index-1; i++){
preNode = preNode.next;
}
Node node = new Node(t);
//要插入的节点的下一个节点指向preNode节点的下一个节点
node.next = preNode.next;
//preNode的下一个节点指向要插入节点node
preNode.next = node;
this.size++;
}
//删除链表元素
public void remove(T t){
if(head == null){
System.out.println("无元素可删除");
return;
}
//要删除的元素与头结点的元素相同
while(head != null && head.t.equals(t)){
head = head.next;
this.size--;
}
/**
* 上面已经对头节点判别是否要进行删除
* 所以要对头结点的下一个结点进行判别
*/
Node cur = this.head;
while(cur != null && cur.next != null){
if(cur.next.t.equals(t)){
this.size--;
cur.next = cur.next.next;
}
else cur = cur.next;
}
}
//删除链表第一个元素
public T removeFirst(){
if(this.head == null){
System.out.println("无元素可删除");
return null;
}
Node delNode = this.head;
this.head = this.head.next;
delNode.next =null;
this.size--;
return delNode.t;
}
//删除链表的最后一个元素
public T removeLast(){
if(this.head == null){
System.out.println("无元素可删除");
return null;
}
//只有一个元素
if(this.getSize() == 1){
return this.removeFirst();
}
Node cur = this.head; //记录当前结点
Node pre = this.head; //记录要删除结点的前一个结点
while(cur.next != null){
pre = cur;
cur = cur.next;
}
pre.next = cur.next;
this.size--;
return cur.t;
}
//链表中是否包含某个元素
public boolean contains(T t){
Node cur = this.head;
while(cur != null){
if(cur.t.equals(t)){
return true;
}
else cur = cur.next;
}
return false;
}
@Override
public String toString() {
StringBuffer sb = new StringBuffer();
Node cur = this.head;
while(cur != null){
sb.append(cur.t+"->");
cur = cur.next;
}
sb.append("NULL");
return sb.toString();
}
public static void main(String[] args) {
Linked<Integer> linked = new Linked();
for(int i = 0; i < 10; i++){
linked.addFirst(i);
System.out.println(linked);
}
linked.addLast(33);
linked.addFirst(33);
linked.add(33, 5);
System.out.println(linked);
linked.remove(33);
System.out.println(linked);
System.out.println("删除第一个元素："+linked.removeFirst());
System.out.println(linked);
System.out.println("删除最后一个元素："+linked.removeLast());
System.out.println(linked);
}
}
总结：学链表是一种痛苦，但是痛苦并快乐着，希望能够坚持下去，把链表的全家桶都学习了，而不是这么简单的增加和删除。上述如有说的不对的地方欢迎指正！下篇文章将进行用链表实现栈和队列。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/130306.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...