前言
今天主要是来模拟单链表的基本功能。
简介
链表是一系列的存储数据元素的单元，通过指针串接起来形成的，因此每个单元至少有两个域，一个域用于数据元素的存储，另一个域是指向其他单元的指针。 这里具有一个数据域和多个指针域的存储单元通常称为 结点（node）
一种最简单的结点结构如图所示，它是构成单链表的基本结点结构。在结点中数据域用来存储数据元素，指针域用于指向下一个具有相同结构的结点。 因为只有一个指针结点，称为单链表。
特点
链表的第一个结点和最后一个结点，分别称为链表的 首结点和 尾结点。 尾结点的特征是其 next 引用为空（null）。 链表中每个结点的 next 引用都相当于一个指针，指向另一个结点， 借助这些 next 引用，我们可以从链表的首结点移动到尾结点。 在单链表中通常使用 head 引用来指向链表的首结点，由 head 引用可以完成对整个链表中所有节点的访问。
在单链表结构中还需要注意的一点是，由于每个结点的数据域都是一个 Object 类的对象，因此，每个数据元素并非真正如图中那样，而是在结点中的数据域通过一个 Object类的对象引用来指向数据元素的。 与数组类似，单链表中的结点也具有一个线性次序，即如果结点 P 的 next 引用指向结点 S，则 P 就是 S 的直接前驱，S 是 P 的直接后续。 单链表的一个重要特性就是只能通过前驱结点找到后续结点，而无法从后续结点找到前驱结点。
单链表的查询、添加、删除操作分析
查询操作
在单链表中进行查找操作，只能从链表的首结点开始，通过每个结点的 next 引用来依次访问链表中的每个结点以完成相应的查找操作。
例如：需要在单链表中查找是否包含某个数据元素 e，则方法是使用一个循环变量 p，起始时从单链表的头结点开始，每次循环判断 p所指结点的数据域是否和 e 相同，如果相同则可以返回 true，否则让p指向下一个节点，继续循环直到链表中所有结点均被访问，此时 p 为 null
关键操作：
- 起始条件：p = head
- 结束条件：
找到：e.equals(p.getData())==true
未找到： p == null - p指向下一个结点: p = p.getNext();
缺点：逐个比较，频繁移动指针，导致效率低下
注意：如果要查询第i个元素的值，无法直接定位，也只能从首结点开始逐个移动到第i个结点，效率同样低下。
添加操作
在单链表中数据元素的插入，是通过在链表中插入数据元素所属的结点来完成的。
对于链表的不同位置，插入的过程会有细微的差别。
中间、末尾的添加过程其实是一样的，关键是在首部添加，会有不同，会改变整个单链表的起始结点。
以添加中间结点为例：
1.指明新结点的后继 s.setNext(p.getNext()); 或者 s.next = p.next
2.指明新结点的前驱（其实是指明前驱结点的后继是新结点） p.setNext(s) 或者 p.next = s;
添加节点不需要移动元素，只需要修改元素的指针即可，效率高。 但是如果需要先查询到添加位置再添加新元素，因为有逐个查询的过程，效率不高。
删除操作
在使用单链表实现线性表的时候，为了使程序更加简洁，我们通常在单链表的最前面添加一个哑元结点，也称为头结点。
在头结点中不存储任何实质的数据对象，其 next 域指向线性表中0号元素所在的结点，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便,常用头结点。
一个带头结点的单链表实现线性表的结构图如图 所示。
单链表的实现
Node
/**
* 单链表的节点
*
* @ClassName Node
* @Description 单链表的节点
* @Author HuangCanCan
* @Date 2019/8/18 19:52
* @Version 1.0
**/
public class Node {
/**
* 要存储的数据
*/
Object data;
/**
* 下一个节点
*/
Node next;
public Node(Object data) {
this.data = data;
}
public Node() {
}
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
SingleLinkedList
/**
* 单链表实现
* <p>
* 核心方法add(inde,e)
*
* @ClassName SingleLinkedList
* @Description 单链表实现
* @Author HuangCanCan
* @Date 2019/8/18 19:50
* @Version 1.0
**/
public class SingleLinkedList implements List {
/**
* 头结点，不存储数据，为了编程方便
*/
private Node head = new Node();
/**
* 节点个数
*/
private int size;
@Override
public int size() {
return size;
}
@Override
public Object get(int index) {
/**
* 链表和顺序表不一样,不能通过索引直接计算定位，而需要从头结点开始进行查找
*/
// 定义一个指针p指向头节点
Node p = head;
for (int i = 0; i <= index; i++) {
p = p.next;
}
return p.data;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean contains(Object e) {
return indexOf(e) >= 0;
}
@Override
public int indexOf(Object e) {
//返回第一次出现的指定元素的索引
Node p = head.next;
if (e == null) {
for (int i = 0; i < size; i++) {
if (p.data == null) {
return i;
}
//移动指针到下一个结点
p = p.next;
}
} else {
for (int i = 0; i < size; i++) {
if (e.equals(p.data)) {
return i;
}
//移动指针到下一个结点
p = p.next;
}
}
return -1;
}
@Override
public void add(int index, Object e) {
//如果i位置错误报异常
if (index < 0 || index > size) {
throw new RuntimeException("数组指针越界异常：" + index);
}
//从head结点开始，找到index的前一个结点，
Node p = head;
for (int i = 0; i < index; i++) {
p = p.next;
}
//新创建一个节点
Node newNode = new Node();
newNode.data = e;
//指明新结点的直接后继结点
newNode.next = p.next;
//指明新结点的直接前驱结点
p.next = newNode;
size++;
}
@Override
public void add(Object e) {
//add(e)是添加元素到单链表末尾，是add(index,e)方法特例，可以如下：
this.add(size, e);
}
@Override
public boolean addBefore(Object obj, Object e) {
//将数据元素 e 插入到元素 obj 之前,元素e是第一次出现的位置
/**
* 第一：找到元素obj的第一次出现位置的前一个节点
* 第二：新建一个节点，指明该新结点的直接后续节点
* 第三：把步骤一得到的节点，指明它的直接后续节点为步骤二新建的节点
* 第四：新数组的长度为数组元素的个数+1
*/
int index = indexOf(obj);
if (index < 0) {
return false;
}
add(index, e);
return true;
}
@Override
public boolean addAfter(Object obj, Object e) {
//将数据元素 e 插入到元素 obj 之后
int index = indexOf(obj);
if (index < 0) {
return false;
}
add(index + 1, e);
return true;
}
@Override
public Object remove(int index) {
//删除线性表中索引为 index 的元素,并返回原数据元素
if (index >= size) {
throw new RuntimeException("索引越界异常：" + index);
}
Object oldValue = this.get(index);
//得到index的前一个节点
Node p = head;
for (int i = 0; i < index; i++) {
p = p.next;
}
//得到index的节点
Node p2 = head;
for (int i = 0; i <= index; i++) {
p2 = p2.next;
}
p.next = p2.next;
size--;
return oldValue;
}
@Override
public boolean remove(Object e) {
//删除第一个与 e 相同的元素
int index = this.indexOf(e);
if (index < 0) {
return false;
}
this.remove(index);
return true;
}
@Override
public Object replace(int index, Object e) {
//替换索引为 index 的数据元素为 e，返回原数据元素
if (index >= size) {
throw new RuntimeException("索引越界异常：" + index);
}
Object oldValue = this.get(index);
Node p = head;
for (int i = 0; i <= index; i++) {
p = p.next;
}
p.data = e;
return oldValue;
}
@Override
public String toString() {
if (size == 0) {
return "[]";
}
StringBuilder builder = new StringBuilder("[");
Node p = head.next;
for (int i = 0; i < size; i++) {
if (i != size - 1) {
builder.append(p.data + ",");
} else {
builder.append(p.data);
}
//移动指针到下一个结点
p = p.next;
}
builder.append("]");
return builder.toString();
}
}
总结
链表和顺序表不一样,不能通过索引直接计算定位，而需要从头结点开始进行查找。
一个简单的结点由一个数据域和一个指针域组成。
为了使程序更加简洁，通常在单链表的最前面添加一个头结点。
头节点的数据域为NULL，尾节点的指针域为NULL。
单链表查询，只能从链表的头结点开始，通过每个结点的 next 引用来依次访问链表中的每个结点。
添加、删除节点不需要移动元素，只需要修改节点相应的指针指向即可。
