Java数据结构-实现单链表的增删查反转和串联操作

这个单链表写了一个月了总算是写出来了，以后可不能再拖延了

本篇是用 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 类见下一页