文章目录[隐藏]
这个单链表写了一个月了总算是写出来了，以后可不能再拖延了 
本篇是用 Java 实现单链表的创建、添加结点（按数据和索引值）、删除结点（按数据和索引值）、打印输出结点、反转单链表和串联单链表。以下全是代码，具体的可以看注释。
SinglyLinkedList.java
//2018年2月27日 SinglyLinkedList.java
package 链表;
import java.util.Random;
import java.util.Scanner;
/**
* 单链表结点类，包含数据 data 和下一个结点的引用 next
* @author sunriseYDY
*/
class Node {
Node next;
int data;
/**
* @param next
* @param data
*/
public Node(Node next, int data) {
this.next = next;
this.data = data;
}
/**
* 设置结点的数据值为参数值
* @param data
*/
public void setData(int data) {
this.data = data;
}
/**
* 从用户的输入中设置数据值
*/
public void setDataByinput() {
int _data;
Scanner in = new Scanner(System.in);
_data = in.nextInt();
data = _data;
}
/**
* 带结点数据的构造方法
* 并且下一个结点为空
* @param data
*/
public Node(int data) {
this.data = data;
this.next = null;
}
/**
* 没有参数的构造方法，默认 下一个结点为空
*/
public Node() {
next = null;
}
}
/**
* 单链表类，类的成员变量有：链表的首结点、尾结点和结点数
* 可以实现单链表的随机产生、插入结点、删除结点、单链表的反转和串联等功能
* @author sunriseYDY
*
*/
class SinglyLinkedList {
private Node first; //首结点
private Node last; //尾结点
private int size = 0; //结点数，即单链表大小
/**
* 默认的构造方法，无参，first=last=null
*/
public SinglyLinkedList() {
first = null;
last = null;
}
/**
*
* @return first，即首结点
*/
public Node getFirst() {
return first;
}
/**
*
* @return last 即尾结点
*/
public Node getLast() {
return last;
}
/**
*
* @return boolean 如果该链表大小为0则返回 true，否则返回 false
*/
public boolean isEmpty() {
if (this.size == 0)
return true;
else
return false;
}
/**
* 插入一个结点，参数为要插入的结点，为 Node 对象
* 如果该链表为空，则让首结点和尾结点都指向新拆入的结点
* 如果该链表不为空，则在末尾插入新的结点
* @param newNode 要插入的新结点
*/
public void insertNode(Node newNode) {
if (isEmpty()) {
newNode.next = null;
this.first = newNode;
this.last = newNode;
}
else {
newNode.next = null;
last.next = newNode;
last = newNode;
}
this.size++; //结点大小加一
}
/**
* 根据参数给出的位置，在指定位置出插入结点
* @param index 要插入位置的索引值，范围为 （1 ~ size+1）,其中 size 为插入前结点总数
* @param newNode 要插入的新的结点
*/
public void insertNodeByindex(int index, Node newNode) {
if (index > this.size + 1) {
System.err.println("Error: out of index");
System.err.println("错误：索引值超过插入后链表结点总数！");
return;
} //如果索引值超过 size+1 , 则提示出错
if (index == 1) {
newNode.next = this.first;
this.first = newNode;
this.size++;
} // 如果索引值为1，则在第一个位置处插入新结点，first 指向新的结点
else {
if (index == ( this.size + 1 ) ) {
last.next = newNode;
last = newNode;
this.size++;
}
else { //如果为其他情况，则先循环到要插入位置的前一个结点
Node current = this.first;
for (int i = 1; i < this.size; i++) {
if ( (i+1) == index) {
break;
}
current = current.next;
}
//将新节点插入到相应位置
newNode.next = current.next;
current.next = newNode;
this.size++; //结点数加一
}
}
}
/**
*
* @return int size 返回单链表的大小
*/
public int getSize() {
return size;
}
/**
* 设置单链表的大小
* @param size
*/
public void setSize(int size) {
this.size = size;
}
public void printSize() {
System.out.println("The size of this linkedList is " + this.getSize());
}
/**
* 打印输出该单链表
*/
public void printASingleLinkedList() {
Node current = first;
while (current != null) {
System.out.printf("%d ", current.data);
current = current.next;
}
System.out.println();
}
/**
* 随机创造出一个单链表，链表结点数为参数 n
* 默认结点数据范围为 0-9
* @param n 链表的结点数
*/
public void randomCreateASingleLinkedList(int n) {
Random random = new Random();
while (n-- != 0) {
Node newNode = new Node(random.nextInt(10));
insertNode(newNode);
}
}
/**
* 从单链表中删除数据为 参数data 的结点，如有多个则删去多个，如果没有就什么也不做
* @param data 要删除的数据
*/
public void deleteANodeByData(int data) {
Node current = first;
//同样的，先判断要删除的数据是否是首结点，然后判断是否是尾结点，最后再循环查找
if (first.data == data) {
first = first.next;
this.size--;
}
if (last.data == data) {
current = first;
while (current.next != last) {
current = current.next;
}
current.next = last.next;
last = current;
this.size--;
}
Node before = first;
current = before.next;
while (current != null) {
if (current.data == data) {
before.next = current.next;
current = current.next;
this.size--;
}
else {
before = current;
current = current.next;
}
}
}
/**
* 根据索引删除指定位置处的结点
* @param index
*/
public void deleteANodeByIndex(int index) {
if (index == 1) {
first = first.next;
this.size--;
}
else {
Node current;
if (index == getSize()) {
current = first;
while (current.next != last) {
current = current.next;
}
current.next = last.next;
last = current;
this.size--;
}
else {
current = first;
for (int i = 1; i <= getSize() ; i++) {
if ( (i+1) == index) {
current.next = current.next.next;
this.size--;
}
current = current.next;
}
}
}
}
/**
* 得到指定索引处的结点数据值
* @param index 索引值
* @return int data
*/
public int getValueOfIndex(int index) {
if (index > getSize()) {
System.err.println("Error: out of index");
System.err.println("错误：索引值超过链表结点总数！");
return 0;
}
else {
Node current = first;
for (int i = 1; i <= getSize(); i++) {
if (i == index) {
return current.data;
}
current = current.next;
}
return 0;
}
}
/**
* 串联另一个单链表，返回给 当前单链表
* @param linkedList2 要串联的单链表，可以是当前单链表对象本身
*/
public void Concatenation(SinglyLinkedList linkedList2) {
//如果两个单链表相同则创建一个新的链表来串联
if (this.last == linkedList2.last) {
SinglyLinkedList tmp = new SinglyLinkedList();
//将单链表一的结点复制到 tmp 链表中
Node current_2 = this.first;
while (current_2 != null) {
tmp.insertNode(new Node(current_2.data));
current_2 = current_2.next;
}
//将单链表二的结点复制到 tmp 中
current_2 = linkedList2.first;
while (current_2 != null) {
tmp.insertNode(new Node(current_2.data));
current_2 = current_2.next;
}
//将 tmp 赋给原来的链表
this.first = tmp.first;
this.last = tmp.last;
this.setSize(tmp.getSize());
}
else {
//如果两个链表不相同则直接将第一个链表的尾结点的 next 指向第二个链表的首结点
this.last.next = linkedList2.first;
this.last = linkedList2.last;
this.setSize(this.getSize() + linkedList2.getSize());
}
}
//清空链表
public void clear() {
this.first = this.last = null;
this.size = 0;
}
//将单链表反转
public void reverseLinkedList() {
Node current = this.first;
Node tmp = first;
Node before = null;
Node beforeBefore = null;
//大致的原理就是每次循环分别有三个结点：当前，上一个，上上一个
//每次循环将上一个的next指向上上一个，然后当前指向当前的next,上一个指向上一个的next
while (current != null) {
beforeBefore = before;
before = current;
current = current.next;
before.next = beforeBefore;
}
first = before;
last = tmp;
}
}
测试用的 Main 类见下一页
赞 (0) -->微信赞赏<--
微信扫描下方左侧二维码或搜索“sunriseydy”关注我的公众号，便捷地阅读博客内容，订阅博客更新
也可以扫描下方右侧的小程序码，进入我的微信小程序：“sunriseydy”，在手机上阅读文章
版权说明：
本作品由 sunriseydy 采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
文章内容如未说明均为原创，欢迎转载，但请注明原作者和出处。部分来自互联网的文章，如有侵权，请联系我，24小时内删除，谢谢
Email：i@mail.sunriseydy.top