【IT168 技术文档】Java描述数据结构第一章向量，[定义1.3指针(pointer)，1.4节点(Node)，1.5单链表，1.6头指针，1.7头节点(哨兵节点)，1.8首元节点，1.9位置(Position)]，[程序1.4单链表节点，1.5位置接口，1.6带头节点的单链表节点实现的向量]。

　　1.4基于单链表节点实现向量

　　1.4.1节点与链表的相关概念

　　[定义1.3]指针(pointer)表示一个数据元素逻辑意义上的存储位置。

　　链式存储结构是基于指针实现的。把一个数据元素和一个指针称为一个[定义1.4]节点(Node)。链式存储结构是用指针把相互关联的节点连接起来的。

　　1.4.2 单链表

　　在[定义1.5]单链表中，构成链表的每个节点只有一个指向直接后继节点的指针。

　　单链表有带头节点结构和不带头节点结构两种。把指向单链表的指针称为单链表的[定义1.6]头指针。头指针所指的不存放数据元素的第一个节点称为[定义1.7]头节点(亦称为哨兵节点)。存放第一个数据元素的节点称为[定义1.8]首元节点。

　　1.4.3带头节点单链表和不带头节点单链表的比较

　　在不带头节点的单链表中，对首元节点的插入和删除操作要区别于其他元素节点插入和删除操作;在带头节点的单链表中，对所有元素节点的插入和删除操作是一致的。

　　1.4.4单链表节点类[程序1.4 Node.java]

　　package com.store.structure;
　　import com.data.structure.position.Position;
　　/**单链表节点*/
　　public class Node implements Position{
　　private Object element;//数据对象

　　private Node next;//指向后继节点

　　public Node(){
　　this(null,null);
　　}
　　public Node(Object e,Node n){
　　element=e;
　　next=n;
　　}
　　//Position Interface

　　/**返回存放于该位置上的元素*/
　　public Object getElem() {
　　return element;
　　}
　　/**将给定元素存放至该位置，返回此前存放的元素*/
　　public Object setElem(Object e) {
　　Object oldElem=element;
　　element=e;
　　return oldElem;
　　}
　　/////////////////////////////////////////////////

　　public Node getNext(){
　　return next;
　　}
　　public void setNext(Node newNext){
　　next=newNext;
　　}
　　}

　　这里抽象出[定义1.9]位置(Position)的概念。基于链式存储结构的节点都应该存在有位置这一概念，这与数组/向量中秩的概念相对应。位置是对列表节点对象的封装。

　　1.4.5位置接口[程序1.5 Position.java]

　　package com.data.structure.position;
　　/**位置*/
　　public interface Position {
　　/**返回存放于该位置上的元素*/
　　public Object getElem();
　　/**将给定元素存放至该位置，返回此前存放的元素*/
　　public Object setElem(Object o);
　　}

　　1.4.6带头节点的代码实现[程序1.6 Vector_Node.java]

　　package com.vector.impl;
　　import com.data.structure.Vector;
　　import com.exception.utils.ExceptionBoundaryViolation;
　　import com.store.structure.Node;
　　/** 基于带头节点的单链表节点实现的向量 */
　　public class Vector_Node implements Vector {
　　private Node head;// 头节点

　　private Node current;// 当前节点

　　private int size;// 数据元素个数

　　public Vector_Node() {
　　head = current = new Node();
　　size = 0;
　　}
　　// Vector interface

　　/** 返回向量中元素数目 */
　　public int getSize() {
　　return size;
　　}
　　/** 判断向量是否为空 */
　　public boolean isEmpty() {
　　return size == 0;
　　}
　　/** 取秩为r的元素 */
　　public Object getAtRank(int r) throws ExceptionBoundaryViolation {
　　checkRank(r, getSize());
　　index(r);
　　return current.getElem();
　　}
　　/** 将秩为r的元素替换为obj */
　　public Object replaceAtRank(int r, Object obj)
　　throws ExceptionBoundaryViolation {
　　checkRank(r, getSize());
　　index(r);
　　Object bak = current.getElem();
　　current.setElem(obj);
　　return bak;
　　}
　　/** 插入obj，作为秩为r的元素，返回该元素 */
　　public Object insertAtRank(int r, Object obj)
　　throws ExceptionBoundaryViolation {
　　checkRank(r, getSize());
　　index(r - 1);
　　current.setNext(new Node(obj, current.getNext()));
　　size++;
　　return obj;
　　}
　　/** 删除秩为r的元素 */
　　public Object removeAtRank(int r) throws ExceptionBoundaryViolation {
　　checkRank(r, getSize());
　　index(r - 1);
　　Object bak = current.getNext().getElem();
　　current.setNext(current.getNext().getNext());
　　size--;
　　return bak;
　　}
　　//assistant methods
　　// 检查秩是否合法

　　private void checkRank(int r, int n) throws ExceptionBoundaryViolation {
　　if (-1 > r || r > n)
　　throw new ExceptionBoundaryViolation("BoundaryViolation");
　　}
　　// 若r的秩合法,则将current定位至秩r;否则报错

　　private void index(int r) throws ExceptionBoundaryViolation {
　　checkRank(r, getSize());
　　int i = 0;
　　if (r == -1) return;// 头节点

　　current = head.getNext();
　　while (i < r){
　　if(current==null) throw new ExceptionBoundaryViolation("BoundaryViolation");
　　current = current.getNext();
　　i++;
　　}
　　}
　　////////////////////////////

　　private static void printAll(Vector v){
　　for(int i=0;i
　　System.out.print(v.getAtRank(i));
　　System.out.println();
　　}
　　//测试

　　public static void main(String[] args){
　　Vector_Node va=new Vector_Node();
　　//测试insert

　　for(int i=0;i<10;i++)
　　va.insertAtRank(0, new Integer(i));
　　printAll(va);
　　//测试remove

　　va.removeAtRank(9);
　　printAll(va);
　　//测试replace

　　va.replaceAtRank(8, 'q');
　　printAll(va);
　　}
　　}

　　1.4.7效率分析

　　设在单链表的任何位置上插入数据元素的概率相等，在单链表中插入一个数据元素时比较数据元素的平均次数为：

　　∑{i从0至n}pi (n-i) =1/(n+1) ∑{i从0至n} (n-i) =n/2

　　删除单链表的一个数据元素时比较数据元素的平均次数为：

　　∑{i从0至n-1}pi (n-i) =1/n ∑{i从0至n-1} (n-i) =(n-1)/2

　　因此，单链表插入和删除操作的时间复杂度均为O(n)。同时，单链表取数据元素操作的时间复杂度也为O(n)。

　　1.4.8优缺点分析

　　基于单链表节点实现的向量(单链表)的主要优点是不需要预先给出数据元素的最大个数。另外，在插入和删除操作时不需要移动数据元素;主要缺点是每个节点都有一个指针，因此单链表的空间利用率略低于基于数组实现的向量;单链表不支持随机读取。