线性表之单链表

前言

线性表的链式存储是用若干地址分散的存储单元存储数据元素，逻辑上相连的数据元素在物理位置上不一定相连，必须采用附加信息表示数据元素之间的关系，并且存储单元至少包含两部分-数据域和地址域

单链表

单链表中结点只有一个地址并且指向后继结点

单链表结点类Node声明如下

public class Node<T> {  //单链表结点类

	public T data;            //数据域，保存数据元素
	public Node<T> next;      //地址域，引用后继结点
	
	public Node(T data,Node<T> next){
		this.data=data;
		this.next=next;
	}
	
	public Node(){
		this(null,null);
	}
}

由于java不支持指针类型，但提供引用方式保存包括地址在内的结构化信息
通常通过node结点建立两个结点之间的链接，如p结点的下一个结点是q结点

Node p=new Node(‘A’,null);
Node q=new Node(‘B’,null);
p.next=q;

单链表的头指针head也是一个结点引用

Node head=null;

当head==null时，为空单链表

单链表的遍历操作
遍历单链表是指从第一个结点开始，沿着结点的next链，依次访问单链表中的每个结点，并且每个结点只访问一次

Node p=head;
while(p!=null){
p=p.next;
}

单链表的插入操作
对单链表进行插入操作，只要该表节点间的链接关系，不需要移动数据元素
空表插入/头插入

if(head==null)
head=new Node(x,null); //空表插入
else{
Node q=new Node(x,null); //头插入
q.next=head;
}

中间插入
若p指向非空单链表的某个结点，在p结点之后插入q结点

< Node q=new Node(x,null);
q.next=p.next; //q的后继结点应是p的原后继结点
p.next=q; //q作为p的后继结点

尾插入

单链表的删除操作
删除单链表的指定结点，只需改变结点的next域

头删除

head=head.next;

中间/尾删除

if(p.next!=null)
p.next=p.next.next;

单链表实现类

public class SinglyLinkenList<T> implements LList<T> {

	public Node<T> head;  //头指针
	
	public SinglyLinkenList(){ //构造空链表
		this.head=new Node<T>();
	}
	
	public SinglyLinkenList(T[] element){//尾插入构造单链表
		this();
		Node<T> rear=this.head; //指向单链表最后一个结点
		for(int i=0;i<element.length;i++){
			rear.next=new Node<T>(element[i],null); //尾插入
			rear=rear.next;     //指向新的链尾结点
		}
		
	}
	
	public boolean isEmpty() {
		
		return this.head.next==null;
	}

	public int length() {
		
		int i=0;
		Node<T> p=this.head.next;  //p从单链表第一个结点开始
		while(p!=null){            //若单链表未结束
			i++;
			p=p.next;             //p的后继结点
		}
		
		return i;
	}
	
	public String toString(){
		String str="(";
		Node<T> p=this.head.next;
		while(p!=null){
			str+=p.data.toString();
			if(p.next!=null)
				str+=",";  //不是最后一个结点时加分隔符
			p=p.next;
		}
		return str+")";
	}

	public T get(int i) {  //返回第i个元素，若i指定序号无效，则返回null
	  if(i>=0)
	  {
		  Node<T> p=this.head.next;
		   for(int j=0;p!=null&&j<i;j++)
			   p=p.next;
		    if(p!=null)
		    	return p.data;
	  }
		
		return null;
	}

	//设置第i个元素值为x，若i指定序号无效则抛出序号越界异常
	public void set(int i, T x) {
		if(x==null)
			return;            //不能设置空对象
		if(i>=0)
		{
			Node<T> p=this.head.next;
			 for(int j=0;p!=null&&j<i;j++)
				 p=p.next;
			 if(p!=null)
				 p.data=x;        //p指向第i个节点
		}
		else throw new IndexOutOfBoundsException(i+"");
		
	}

	public void insert(int i, T x) {//将x对象插入在序号为i的结点前

		if(x==null)
			return;
		Node<T> p=this.head;  //p指向头结点
		for(int j=0;p.next!=null&&j<i;j++) //寻找插入位置
			p=p.next;  //循环停止时，p指向第i-1结点或最后一个结点
		p.next=new Node<T>(x,p.next);
		
	}

	//单链表最后添加对象
	public void append(T x) {
		insert(Integer.MAX_VALUE,x);
		
	}

	
	public T remove(int i) {
		if(i>=0)
		{
			Node<T> p=this.head;
			 for(int j=0;p.next!=null&&j<i;j++)//找到待删除的结点i的前驱结点i-1
				 p=p.next;
			 if(p.next!=null)
			 {
				 T old=p.next.data;     //获取原对象
				  p.next=p.next.next;    //删除p的后继结点
				   return old;
			 }
		}
		return null;
	}

	public void removeAll() {
	this.head.next=null;
		
	}

	public int indexOf(T key) {
		// TODO Auto-generated method stub
		return 0;
	}

	public boolean contain(T key) {
		
		return this.search(key)!=null;
	}

	public T search(T key) {
	 if(key==null)
		 return null;
	 Node<T> p=this.head.next;
	 while(p!=null)
	 {
		 if(p.data.equals(key))
			 return p.data;
		 p=p.next;
	 }
		return null;
	}

}

单链表求解约瑟夫环

只需更改一处

//LList list=new seqList(number);
LList list=new SinglyLinkenList();

得到如下结果

初始化约瑟夫环:(5,0,2)
删除B(A,C,D,E)
删除D(A,C,E)
删除A(C,E)
删除E(C)
最后的被赦免者是:C

此外单链表相比较于顺序表在插入和删除时只要改变少量结点的链，不需要移动数据元素，也避免了顺序表因存在空间不足扩充空间和复制元素的过程，提高了运行效率和空间利用率