Java数据结构-线性表之单链表LinkedList

线性表的链式存储结构，也称之为链式表，链表；链表的存储单元可以连续也可以不连续。
链表中的节点包含数据域和指针域，数据域为存储数据元素信息的域，指针域为存储直接后继位置（一般称为指针）的域。注意一个头结点和头指针的区别：
头指针：

指向链表的第一个节点的指针，若链表有头结点，则是指向头结点的指针；
头指针具有标识作用，所以常用头指针作为链表的名字；
不论链表是否为空，头指针都不为空；
是链表的必要元素。

头结点：

头结点是为了操作的统一和方便而设立的，放在第一个元素节点的前面，其数据域一般无意义，也可以存放链表的长度；
头结点不是链表的必要元素。

这里先讲讲单链表吧，其他的后面再讲。
无头结点的链表

有头结点的链表

空链表
我试着用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;}}@Overridepublic 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;}@Overridepublic String toString（） {return "Node [e=" + e + ", next=" + next + "]";}}

这里也讲讲数据元素的插入和删除操作；
插入操作演示如下：

代码：s->next = p->next;p->next = s;这里摘了《大话数据结构》的一段文字解释：
删除操作如下图：
一句代码：p->next = p->next->next;结合上述代码和图例，可以看出单链表的删除和插入操作都是由两部分组成：

遍历查找到需要操作的位置的那个元素；
然后进行插入和删除操作。

下面是摘自《大话数据结构》的分析：
单链表的整表创建
方法有头插法和尾插法；
头插法：相当于插队的方法。如下图
相对于头插法，尾插法更加合理一些。单链表的整表删除
下面是摘自《大话数据结构》的分析：

下面比较一下单链表和顺序表：
本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-07/120144.htm