线性表的链式存储结构，也称之为链式表，链表；链表的存储单元能够连续也能够不连续。
链表中的节点包括数据域和指针域。数据域为存储数据元素信息的域，指针域为存储直接后继位置（一般称为指针）的域。
注意一个头结点和头指针的差别：
头指针：
- 指向链表的第一个节点的指针。若链表有头结点，则是指向头结点的指针；
- 头指针具有标识作用，所以经常使用头指针作为链表的名字；
- 不论链表是否为空，头指针都不为空；
- 是链表的必要元素。
头结点：
- 头结点是为了操作的统一和方便而设立的。放在第一个元素节点的前面，其数据域一般无意义，也能够存放链表的长度；
- 头结点不是链表的必要元素。
这里先讲讲单链表吧。其它的后面再讲。
无头结点的链表
有头结点的链表
空链表
我试着用Java写了一个LinkedList的代码，例如以下：
package com.phn.datestructure;
/**
* @author 潘海南
* @Email 1016593477@qq.com
* @TODO 链式表
* @date 2015年7月18日
*/
public class FOLinkedList<E> {
// 单链表的头结点
private FOLinkedNode<E> header = null;
// 单链表的长度
private int size;
/**
* @TODO 默认的无參构造函数
*/
public FOLinkedList() {
super();
this.header = new FOLinkedNode<E>();
this.setSize();
}
/**
* @TODO 单链表加入元素
* @param e 数据元素类型
* @return true
*/
public boolean add(E e) {
FOLinkedNode<E> node = new FOLinkedNode<E>(e);
if (header.getE() == null) {
header.setE(e);
} else {
FOLinkedNode<E> lastNode = this.last(this.header);
lastNode.addNext(node);
}
this.size++;
return true;
}
/**
* @TODO 单链表插入元素
* @param index 插入位置
* @param e 数据元素类型
* @return true
*/
public boolean insert(int index,E e) {
FOLinkedNode<E> node = new FOLinkedNode<E>(e);
FOLinkedNode<E> preNode = this.get(index - 1);
node.addNext(preNode.next);
preNode.addNext(node);
this.size++;
return true;
}
/**
* @TODO 单链表删除元素
* @param index 将要删除的元素的索引位置
* @return E 删除的元素
*/
public FOLinkedNode<E> remove(int index){
FOLinkedNode<E> preNode = this.get(index-1);
FOLinkedNode<E> node = preNode.next;
preNode.addNext(preNode.next.next);
node.addNext(null);
this.size--;
return node;
}
/**
* @TODO 依据元素索引位置获取元素
* @param index 元素的索引位置
* @return E 元素e
*/
public FOLinkedNode<E> get(int index) {
validateIndex(index);
FOLinkedNode<E> temp = this.header;
int i = 0;
while (i < index - 1) {
if (temp != null) {
temp = temp.next;
i++;
} else {
throw new RuntimeException("节点空值错误");
}
}
return temp;
}
/**
* @TODO 将单链表中索引位置为i的元素改动为元素e
* @param index 元素的索引位置
* @param e 须要改动成的元素
* @return true 改动成功标志
*/
public boolean set(int index, E e){
validateIndex(index);
FOLinkedNode<E> oldNode = this.get(index);
oldNode.setE(e);
return true;
}
/**
* @TODO 验证所给索引位置是否合法
* @param index 给出的索引位置
*/
private void validateIndex(int index) {
if (index > this.size || index < 0) {
throw new RuntimeException("索引错误：" + index);
}
}
/**
* @TODO 获取单链表的最后一个节点
* @param header 单链表的头结点
* @return node 单链表的最后一个节点
*/
private FOLinkedNode<E> last(FOLinkedNode<E> header) {
FOLinkedNode<E> temp = header;
while (true) {
if (temp.next == null) {
return temp;
}
temp = temp.next;
}
}
@Override
public String toString() {
return "[" + this.NodesToString(this.header) + "]";
}
/**
* @TODO 设置单链表的长度
* @param header 单链表的头结点
* @return 单链表的节点字符串序列
*/
private String NodesToString(FOLinkedNode<E> header) {
StringBuffer sb = new StringBuffer();
if (header != null) {
sb.append(header.getE());
FOLinkedNode<E> temp = new FOLinkedNode<E>();
temp = header.next;
while (temp != null) {
sb.append(", " + temp.getE());
temp = temp.next;
}
}
return sb.toString();
}
/**
* @TODO 设置单链表的长度
*/
private void setSize() {
this.size = 0;
}
/**
* @TODO 获取单链表的长度
* @return size 单链表的长度
*/
public int size() {
return this.size;
}
}节点类：
package com.phn.datestructure;
public class FOLinkedNode<E> {
private E e;// 结点中存放的数据
FOLinkedNode() {
}
FOLinkedNode(E e) {
this.e = e;
}
FOLinkedNode<E> next;// 用来指向该结点的下一个结点
// 设置下一节点的值
void addNext(FOLinkedNode<E> node) {
next = node;
}
public E getE() {
return e;
}
public void setE(E e) {
this.e = e;
}
@Override
public String toString() {
return "Node [e=" + e + ", next=" + next + "]";
}
}这里也讲讲数据元素的插入和删除操作。
插入操作演演示样例如以下：
代码：
s->next = p->next;
p->next = s;
这里摘了《大话数据结构》的一段文字解释：
删除操作例如以下图：
一句代码：
p->next = p->next->next;
结合上述代码和图例。能够看出单链表的删除和插入操作都是由两部分组成：
- 遍历查找到须要操作的位置的那个元素；
- 然后进行插入和删除操作。
以下是摘自《大话数据结构》的分析：
单链表的整表创建
方法有头插法和尾插法；
头插法：相当于插队的方法。例如以下图
相对于头插法。尾插法更加合理一些。
单链表的整表删除
以下是摘自《大话数据结构》的分析：
以下比較一下单链表和顺序表：