线性表的链式存储结构，也称之为链式表，链表；链表的存储单元可以连续也可以不连续。
链表中的节点包含数据域和指针域，数据域为存储数据元素信息的域，指针域为存储直接后继位置（一般称为指针）的域。
注意一个头结点和头指针的区别：
头指针：
指向链表的第一个节点的指针，若链表有头结点，则是指向头结点的指针；
头指针具有标识作用，所以常用头指针作为链表的名字；
不论链表是否为空，头指针都不为空；
是链表的必要元素。
头结点：
头结点是为了操作的统一和方便而设立的，放在第一个元素节点的前面，其数据域一般无意义，也可以存放链表的长度；
头结点不是链表的必要元素。
这里先讲讲单链表吧，其他的后面再讲。
无头结点的链表
有头结点的链表
空链表
我试着用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; } }