一、单链表的概念

单链表的概念：单链表是一种链式存取的数据结构，链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。以“结点的序列”表示的线性表称作线性链表（单链表），单链表是链式存取的结构。

具体而言

单链表由头结点和元素结点连接组成。

单链表的每个结点由数据域和指针域组成。数据域存储数据，指针域存储下一个结点的地址。

单链表的最后一个结点的指针域指向空（NULL）。

头结点的作用：

统一操作--由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置的结点的操作一样，无需做其他特殊处理。
统一判空--链表为空时，头结点的指针域指向空，即可判空，链表不为空时，头结点的指针域指向第一个元素结点，头结点的指针域不为空，即可判不空。

二、单链表的实现

1.定义节点类

package com.zsj1105;public class Node<E> {public E value;   //存储结点的值public Node next;   //用来存储下一个结点的地址//空参构造方法public Node(){}//有参构造方法public Node(E value,Node next){//每个结点都有一个数据域和地址域this.value = value;this.next = next;}}

2.定义单链表

1.属性

* head 头部结点

* tail 尾部结点

* curr 当前结点

* size 元素个数

    //属性private Node<E> head;  //设置头部结点private Node<E> tail;  //设置尾部结点private Node<E> curr;  //设置当前结点private int size;  //设置元素个数

2.方法

（1）构造方法

* 1.NodeList() 空参数构造方法
* 2.NodeList(Node node) 由一个结点创建一个链表

 //构造方法/*** 无参数构造方法*/NodeList() {head = tail = curr = new Node();size = 0;}/*** 由一个结点创建链表** @param node*/NodeList(Node node) {head = tail = curr = new Node();this.size = 1;this.head.next = node;this.tail = node;}

（2）方法

* 1.int getSize() 获取总元素个数
* 2.Node getHead() 获取头部结点
* 3.Node getCurr() 获取当前结点
* 4.Node getTail() 获取尾部结点
* 5.void setCurr() 设置当前结点
* 6.void print() 打印链表中的所有元素
* 7.void addToHead(E value)在头部结点后面插入结点
* 8.void addToTail(E value)在尾部结点后面插入结点
* 9.void insert(E value)将当前结点值设为value
* 10.delete()删除当前结点之后的一个结点
* 11.delete(E value)删除第一个值为value的结点
* 12.find(E value)找到值为value的结点
* 13.replace(E value)将当前结点的值替换为value
* 14.replace(E value1, E value2)将值为value1的结点的值替换为value2

  //方法/*** 获取元素个数** @return*/public int getSize() {return size;}/*** 获取头部结点** @return*/public Node<E> getHead() {return head;}/*** 获取当前结点** @return*/public Node<E> getCurr() {return curr;}/*** 获取尾部结点** @return*/public Node<E> getTail() {return tail;}/*** 设置当前结点为指定结点** @param curr*/public void setCurr(Node curr) {this.curr = curr;}/*** 打印出链表中的所有元素*/public void print() {if (size == 0)System.out.println("链表中没有元素");else {this.curr = this.head.next;System.out.print("单链表中的元素:head-");while (this.curr != null) {System.out.print(this.curr.value + "-");this.curr = this.curr.next;}System.out.println("null");System.out.println("元素个数" + this.size);}}/*** 在头部结点之后插入结点** @param value*/public void addToHead(E value) {if (size == 0) {this.tail = new Node(value, null);this.head.next = this.tail;} elsethis.head.next = new Node(value, this.head.next);size++;}/*** 在尾部结点之后插入结点** @param value*/public void addToTail(E value) {if (size == 0) {this.tail = new Node(value, null);this.head.next = this.tail;} else {this.tail.next = new Node(value, null);this.tail = this.tail.next;}size++;}/*** 在当前结点后面插入结点** @param value*/public void insert(E value) {if (this.curr == this.head) {addToHead(value);} else if (this.curr == this.tail) {this.curr.next = new Node(value, null);this.tail = this.curr.next;size++;} else {this.curr.next = new Node(value, this.curr.next);size++;}}/*** 删除当前结点之后的一个结点*/public void delete() {if (this.curr == this.tail) {System.out.println("超出范围");} else if (size == 0) {System.out.println("链表中没有元素");} else if (this.curr.next == this.tail) {this.curr.next = null;this.tail = this.curr;size--;System.out.println("删除成功");} else {this.curr.next = this.curr.next.next;size--;System.out.println("删除成功");}}/*** 删除值为value的结点** @param value*/public void delete(E value) {int count = 0;if (size == 0) {System.out.println("链表中没有元素");} else if (size == 1) {if (this.tail.value.equals(value)) {this.head.next = null;this.tail = this.head;size--;}} else {this.curr = this.head;while (this.curr.next != null) {if (this.curr.next.value.equals(value)) {if (this.curr.next.next == null) {this.curr.next = null;} else {this.curr.next = this.curr.next.next;}size--;count++;System.out.println("删除成功");continue;}this.curr = this.curr.next;}System.out.println("一共删除了" + count + "个结点");}}/*** 返回第一个值为value的结点或者boolean** @param value* @return*/public Node find(E value) {if (size == 0) {System.out.println("链表中无元素");return null;}this.curr = this.head.next;while (this.curr != null) {if (this.curr.value.equals(value)) {return this.curr;}this.curr = this.curr.next;}System.out.println("链表中没有这个元素");return null;}/*** 将当前结点的值替换为value** @param value*/public void replace(E value) {if (size == 0) {System.out.println("链表中没有元素");}if (this.curr == this.head) {System.out.println("当前位置(在头部结点)不合法");}this.curr.value = value;}/*** 将所有value1替换为value2** @param value1* @param value2*/public void replace(E value1, E value2) {int count = 0;if (size == 0) {System.out.println("链表中没有元素");}this.curr = this.head.next;while (this.curr != null) {if (this.curr.value.equals(value1)) {this.curr.value = value2;count++;}this.curr = this.curr.next;}System.out.println("一共完成了" + count + "次替换");

三、完整实现

package com.zsj1105;import javax.swing.*;/*** NodeList 链表类，结点串联(首结点不存元素)* 一、属性* 1.head 头部结点* 2.tail 尾部结点* 3.curr 当前结点* 4.size 元素个数* <p>* 二、构造方法* 1.NodeList() 空参数构造方法* 2.NodeList(Node node) 由一个结点创建一个链表* <p>* 三、方法* 1.int getSize() 获取总元素个数* 2.Node getHead() 获取头部结点* 3.Node getCurr() 获取当前结点* 4.Node getTail() 获取尾部结点* 5.void setCurr() 设置当前结点* 6.void print() 打印链表中的所有元素* 7.void addToHead(E value)在头部结点后面插入结点* 8.void addToTail(E value)在尾部结点后面插入结点* 9.void insert(E value)将当前结点值设为value* 10.delete()删除当前结点之后的一个结点* 11.delete(E value)删除第一个值为value的结点* 12.find(E value)找到值为value的结点* 13.replace(E value)将当前结点的值替换为value* 14.replace(E value1, E value2)将值为value1的结点的值替换为value2*/
public class NodeList<E> {//属性private Node<E> head;  //设置头部结点private Node<E> tail;  //设置尾部结点private Node<E> curr;  //设置当前结点private int size;  //设置元素个数//构造方法/*** 无参数构造方法*/NodeList() {head = tail = curr = new Node();size = 0;}/*** 由一个结点创建链表** @param node*/NodeList(Node node) {head = tail = curr = new Node();this.size = 1;this.head.next = node;this.tail = node;}//方法/*** 获取元素个数** @return*/public int getSize() {return size;}/*** 获取头部结点** @return*/public Node<E> getHead() {return head;}/*** 获取当前结点** @return*/public Node<E> getCurr() {return curr;}/*** 获取尾部结点** @return*/public Node<E> getTail() {return tail;}/*** 设置当前结点为指定结点** @param curr*/public void setCurr(Node curr) {this.curr = curr;}/*** 打印出链表中的所有元素*/public void print() {if (size == 0)System.out.println("链表中没有元素");else {this.curr = this.head.next;System.out.print("单链表中的元素:head-");while (this.curr != null) {System.out.print(this.curr.value + "-");this.curr = this.curr.next;}System.out.println("null");System.out.println("元素个数" + this.size);}}/*** 在头部结点之后插入结点** @param value*/public void addToHead(E value) {if (size == 0) {this.tail = new Node(value, null);this.head.next = this.tail;} elsethis.head.next = new Node(value, this.head.next);size++;}/*** 在尾部结点之后插入结点** @param value*/public void addToTail(E value) {if (size == 0) {this.tail = new Node(value, null);this.head.next = this.tail;} else {this.tail.next = new Node(value, null);this.tail = this.tail.next;}size++;}/*** 在当前结点后面插入结点** @param value*/public void insert(E value) {if (this.curr == this.head) {addToHead(value);} else if (this.curr == this.tail) {this.curr.next = new Node(value, null);this.tail = this.curr.next;size++;} else {this.curr.next = new Node(value, this.curr.next);size++;}}/*** 删除当前结点之后的一个结点*/public void delete() {if (this.curr == this.tail) {System.out.println("超出范围");} else if (size == 0) {System.out.println("链表中没有元素");} else if (this.curr.next == this.tail) {this.curr.next = null;this.tail = this.curr;size--;System.out.println("删除成功");} else {this.curr.next = this.curr.next.next;size--;System.out.println("删除成功");}}/*** 删除值为value的结点** @param value*/public void delete(E value) {int count = 0;if (size == 0) {System.out.println("链表中没有元素");} else if (size == 1) {if (this.tail.value.equals(value)) {this.head.next = null;this.tail = this.head;size--;}} else {this.curr = this.head;while (this.curr.next != null) {if (this.curr.next.value.equals(value)) {if (this.curr.next.next == null) {this.curr.next = null;} else {this.curr.next = this.curr.next.next;}size--;count++;System.out.println("删除成功");continue;}this.curr = this.curr.next;}System.out.println("一共删除了" + count + "个结点");}}/*** 返回第一个值为value的结点或者boolean** @param value* @return*/public Node find(E value) {if (size == 0) {System.out.println("链表中无元素");return null;}this.curr = this.head.next;while (this.curr != null) {if (this.curr.value.equals(value)) {return this.curr;}this.curr = this.curr.next;}System.out.println("链表中没有这个元素");return null;}/*** 将当前结点的值替换为value** @param value*/public void replace(E value) {if (size == 0) {System.out.println("链表中没有元素");}if (this.curr == this.head) {System.out.println("当前位置(在头部结点)不合法");}this.curr.value = value;}/*** 将所有value1替换为value2** @param value1* @param value2*/public void replace(E value1, E value2) {int count = 0;if (size == 0) {System.out.println("链表中没有元素");}this.curr = this.head.next;while (this.curr != null) {if (this.curr.value.equals(value1)) {this.curr.value = value2;count++;}this.curr = this.curr.next;}System.out.println("一共完成了" + count + "次替换");}public static void main(String[] args) {NodeList<Integer> nodeList = new NodeList<Integer>(new Node<Integer>(520, null));
//        for (int i = 0; i < 20; i++) {
//            nodeList.addToHead(i);
//            nodeList.print();
//        }
//        System.out.println(nodeList.size);
//        System.out.println(nodeList.getTail().value);
//        for (int i = 0; i < 20; i++) {
//            nodeList.addToTail(i);
//            nodeList.print();
//        }//        nodeList.addToHead(5);
//        System.out.println(nodeList.size);
//        nodeList.addToHead(250);
//        System.out.println(nodeList.size);
//        nodeList.addToHead(270);
//        System.out.println(nodeList.size);
//        nodeList.delete(520);
//        nodeList.print();for (int i = 0; i < 5; i++) {nodeList.addToHead(i);}
//        nodeList.print();
//        nodeList.delete(0);
//        nodeList.print();nodeList.delete(520);}
}