线性表的链式存储是用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻。
带头结点的单链表是指，在单链表的第一个结点之前增加一个特殊的结点，称为头结点。
头结点的作用：使所有链表（包括空表）的头指针非空，并使对单链表的插入，删除操作不需要区分是否为空表或是否在第一个位置进行，从而与其他位置的插入，删除操作一致。

基本操作：
接口里的方法声明：

public interface ICLinked {void addFirst(int data);//头插法void addLast(int data);//尾插法boolean addindex(int index,int data);//任意位置插入，第一个数据结点为0号下标boolean contains(int key);   //查找是否包含关键字key是否在单链表当中int remove(int key) throws Exception;  //删除第一次出现关键字为key的结点void removeAllKey(int key);//删除所有值为key的结点int getLength();void display();void clear();}

方法的具体实现：
public class HeadSingleList implements ICLinked {
class Node {
private int data;
private Node next;

    //头结点public Node() {this.data = -1;}//数据结点public Node(int data) {this.data = data;}public int getData() {return data;}
}private Node head;public HeadSingleList() {this.head = new Node();this.head.next = this.head;}@Overridepublic void addFirst(int data) {Node node = new Node(data);node.next = this.head.next;  //不需要区分是否为空表或是否在第一个位置进行this.head.next = node;}@Overridepublic void addLast(int data) {Node node = new Node(data);Node currency = this.head;while (currency.next != this.head) {currency = currency.next;}node.next=currency.next;currency.next=node;}//index-1的位置private Node SearchIndex(int index) {checkindex(index);Node cur = this.head.next;for(int i=0;i<index;i++) {cur = cur.next;}return cur;}private void checkindex(int index) {if (index < 0 || index > getLength()) {throw new UnsupportedOperationException();}}public boolean addindex(int index, int data) {Node p = SearchIndex(index);Node node = new Node(data);node.next = p.next;p.next = node;return true;}@Overridepublic boolean contains(int key) {Node currency = this.head.next;while (currency != this.head) {if (currency.data == key) {return true;}currency = currency.next;}return false;}private Node searchPre(int key) {Node p = this.head;  //找前驱while (p.next !=this. head) {if (p.next.data == key) {return p;}p = p.next;}return null;   //找不到返回空}@Overridepublic int remove(int key) {Node p = searchPre(key);  //找前驱if (p == null) {throw new UnsupportedOperationException();}Node del = p.next;int oddata = del.data;   //保存p.next = del.next;  //p.next=p.next.nextreturn oddata;}@Overridepublic void removeAllKey(int key) {Node p = this.head;Node currency = this.head.next;while (currency != this.head) {if (currency.data == key) {p.next = currency.next;currency = p.next;} else {p = currency;currency = currency.next;}}}@Overridepublic int getLength() {int length = 0;Node currency = this.head.next;  //currency指向第一个数据结点while (currency != this.head) {length++;currency = currency.next;}return length;}@Overridepublic void display() {Node currency = this.head.next;while (currency != head) {System.out.print(currency.data + " ");currency = currency.next;}System.out.println();}@Overridepublic void clear() {while (this.head.next != this.head) {Node currency = this.head.next;this.head.next = currency.next;}//头结点置为空this.head = null;}

测试：

        public static void main(String[] args) {HeadSingleList headsingle = new HeadSingleList();headsingle.addFirst(3);headsingle.addFirst(5);headsingle.addFirst(8);headsingle.addFirst(9);headsingle.display();headsingle.addLast(6);headsingle.addLast(7);headsingle.addLast(9);headsingle.display();headsingle.addindex(1, 10);headsingle.display();System.out.println(headsingle.contains(7));System.out.println(headsingle.remove(7));headsingle.display();headsingle.removeAllKey(9);headsingle.display();}}

运行结果：