在上一篇文章中，我们讲了 Java 的 LinkedList 的源码，今天我们就自己来实现一个单链表。
话不多说，直接上代码。
代码语言：javascript复制public class SingleLinkedList<T> {
private static final int DEFAULT_LIST_SIZE = 0;
// 头结点
private Node<T> head;
// 尾结点
private Node<T> tail;
private int length = DEFAULT_LIST_SIZE;
// 结点Node 单链表: 只包含一个value和next
public static class Node<T> {
// 结点值
private T value;
// 下一个结点
private Node<T> next;
public Node(T value, Node<T> next) {
this.value = value;
this.next = next;
}
// 只是为了方便打印
@Override
public String toString() {
return "Node{"
"value=" value
'}';
}
}
/**
* 添加头结点
* @param value 结点值
* @return 头结点
*/
public Node<T> addHead(T value) {
Node<T> node = new Node<>(value, null);
node.next = head; // 只需要将新结点的next指向原头结点就可以了
head = node; // 更新头结点
length ; // 长度加1
return node;
}
/**
* 添加尾结点
* @param value 结点值
* @return 尾结点
*/
public Node<T> addTail(T value) {
if (head == null) {
head = new Node<>(value, null);
length ;
tail = head;
return head;
}
Node<T> node = add(value, length);
tail = node;
return node;
}
/**
* 在尾部添加新结点
* @param value 结点值
* @return 新结点的值
*/
public Node<T> add(T value, int index) {
if (index > length || index < 1 ) {
return null;
}
Node<T> newNode = new Node<>(value, null); // 创建一个新结点
int curIndex = 1;
Node<T> curNode = head; // 从头结点开始遍历
while (curNode.next != null) {
if (curIndex == index) {
break; // 不在里面删除的主要原因是避免curNode是尾结点的是时候，不能进来
}
curNode = curNode.next;
curIndex ;
}
newNode.next = curNode.next;
curNode.next = newNode;
length ;
return null;
}
/**
* 删除头结点
* @return 头结点的值
*/
public T removeHead() {
if (head == null) {
return null;
}
T value = head.value;
head = head.next;
if (length == 1) {
tail = null;
}
length--;
return value;
}
/**
* 删除尾结点
* @return 尾结点的值
*/
public T removeTail() {
if (head == null || length == 1) {
T value = head == null ? null : head.value;
head = null;
length--;
return value;
}
Node<T> preNode = head;
Node<T> curNode = head.next;
while (curNode.next != null) {
preNode = curNode;
curNode = curNode.next;
}
preNode.next = null;
length--;
tail = preNode;
return curNode.value;
}
/**
* 删除指定结点
* @param index 序号
* @return 结点的值
*/
public T remove(int index) {
if (index > length || length < 1 || head == null) {
return null;
}
if (index == 1) { // 序号为1,直接返回头结点
return removeHead();
}
int curIndex = 2; // 当前序号, 因为上面已经返回了头结点,所以从第二个结点开始
Node<T> preNode = head; // 记录上一个结点,便于删除
Node<T> curNode = head.next; // 当前需要删除的绩点
while (curNode != null) { // 遍历
if (curIndex == index) { // 当前序号为需要删除的序号的时候
preNode.next = curNode.next; // 直接将当前结点next赋值前结点的next, 删除结点的常规操作
if (index == length) { // 如果序号的长度等于链表长度
tail = preNode;
}
length--; // 链表-1
return curNode.value;
}
preNode = curNode; // 为下一个遍历做准备, 当前结点变成前一个结点
curNode = curNode.next; // 获取下一个结点
curIndex ;
}
return null;
}
/**
* 获取指定序号的结点值
* @param index 序号
* @return 值
*/
public T get(int index) {
if (index > length || index < 1 || head == null) {
return null;
}
if (index == 1) { // 头结点,不需要遍历
return head.value;
}
if (index == length) { // 尾结点,也不需要遍历了
return tail.value;
}
int tempIndex = 2; // 当前序号, 因为上面已经返回了头结点,所以从第二个结点开始
Node<T> curNode = head.next; // 当前序号
while (curNode.next != null) {
if (tempIndex == index) { // 找到了指定序号的结点
return curNode.value;
}
curNode = curNode.next; // 获取写一个结点
tempIndex ;
}
return null;
}
public int size() {
return length;
}
public Node<T> getHead() {
return head;
}
public void setHead(Node<T> head) {
this.head = head;
}
public Node<T> getTail() {
return tail;
}
public void setTail(Node<T> tail) {
this.tail = tail;
}
/**
* 打印链表
*/
public void printLinkedList() {
StringBuilder sb = new StringBuilder();
if (head == null) {
System.out.println("empty list");
return;
}
Node<T> node = head;
while (node.next != null) {
sb.append(node.value).append("->");
node = node.next;
}
sb.append(node.value);
System.out.println(sb.toString());
}
}代码测试
代码语言：javascript复制public static void main(String[] args) {
SingleLinkedList<Integer> linkedList = new SingleLinkedList<>();
linkedList.printLinkedList();
linkedList.addTail(1);
linkedList.addTail(2);
linkedList.addTail(3);
linkedList.addTail(4);
linkedList.addTail(5);
linkedList.addTail(6);
linkedList.addHead(0);
System.out.print("原始链表: ");
linkedList.printLinkedList();
System.out.println("原始链表长度: " linkedList.size());
int index = linkedList.size() - 2;
linkedList.remove(index);
System.out.print("删除第" index "个结点后的链表: ");
linkedList.printLinkedList();
System.out.println("删除第" index "个结点后的链表长度: " linkedList.size());
linkedList.removeHead();
System.out.print("删除头结点后的链表: ");
linkedList.printLinkedList();
System.out.println("删除头结点后的链表长度: " linkedList.size());
System.out.println("头结点" linkedList.getHead());
System.out.println("尾结点" linkedList.getTail());
linkedList.removeTail();
System.out.print("删除尾结点后的链表: ");
linkedList.printLinkedList();
System.out.println("删除尾结点后的链表长度: " linkedList.size());
int getIndex = linkedList.size() - 1;
System.out.println("获取第" getIndex "个结点: " linkedList.get(getIndex));
int nullIndex = linkedList.size() 1;
System.out.println("获取第" nullIndex "个结点: " linkedList.get(nullIndex));
System.out.println("尾结点" linkedList.getTail());
}代码输出
