数据结构之链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
数组是连续的 线性的存储结构。

链表由一系列结点（链表中每个元素或对象称为结点）组成，结点可以在运行时动态生成。每个结点包括链各个部
分:一个是存储数据元素的数据源，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，链表比较方便插入
和删除操作。

单链表：
//单向链表结点类
public class LinkNode{

private Object obj;//结点内的数据对象
private LinkNode nextNode;//对下一个结点的引用

//构造方法  构建结点类的时候把对象传入
public LinkNode(Object obj){
this.obj = obj;
}

//返回下一个结点对象
public LinkNode getnext(){
return nextNode;
}

//设置下一个结点对象
public void setnext(LinkNode nextNode){
this.nextNode = nextNode;
}
//设置结点对象
public void setnode(Object obj){
this.obj = obj;
}

}

实现单向链表
//返回根结点
public LinkNode creatLink(){
//以字符串对象为例
String s = "根节点" ;
LinkNode root = new LinkNode(s);//根结点
LinkNode n1  = new LinkNode("一节点");
LinkNode n1  = new LinkNode("二节点");
LinkNode n1  = new LinkNode("三节点");
LinkNode n1  = new LinkNode("四节点");
root.setnext(n1);
n1.setnext(n2);
n2.setnext(n3);
n3.setnext(n4);

return root;
}


双向链表:双向式单向链表的改进   在双向链表中，结点除含有数据域外，还有两个链域，一个存储子结点地址，
一般称之为右链域；一个存储父结点地址，一般称之为左链域。

链表实现自定义队列：实现数据的插入、删除、修改、取出····

插入：将要插入位置的原结点的父结点的nextNode指向要插入的对象，再将要插入的对象的nextNode指向
原结点。（双向链表同理）
删除：将要删除位置的结点的父结点指向该位置结点的子结点。
修改：在结点类中写相应的set方法，在修改函数中直接调用。
取出：循环读取。


结点类：

public class Node {
//	节点存储的数据
	private Object date;
//	上一个节点的地址
	private Node privous;
//	下一个节点的地址
	private Node next;
	
public Node() {
		super();
	}
//	构造函数
public Node(Object date) {
		super();
		this.date = date;
	}
	//	返回节点处的数据
	public Object getDate() {
		return date;
	}
//	设置节点处的数据
	public void setDate(Object date) {
		this.date = date;
	}
//	返回上一个节点
	public Node getPrivous() {
		return privous;
	}
//	设置上一个节点
	public void setPrivous(Node privous) {
		this.privous = privous;
	}
//	返回下一个节点
	public Node getNext() {
		return next;
	}
//	设置上一个节点
	public void setNext(Node next) {
		this.next = next;
	}


}

链表类：

public class LinkedList {
	
//	链表长度
	private int size=0;
//	根节点
	private Node root=null;
//	尾节点
	private Node last=null;
//	构造函数
	public LinkedList() {
		super();
	}
//	带参构造函数
	public LinkedList(int size){
		this.size = size;
	}
//	带参构造函数
	public LinkedList(int size, Node root, Node last) {
		this.size = size;
		this.root = root;
		this.last = last;
	}
	
//	添加节点到链表的末尾
	public void add(Node node){
		if(root==null){
			root = node;
			last = node;
		}
		else {
			 last.setNext(node);
			 node.setPrivous(last);
			 last = node;
		}
		size++;
	}
//返会索引位置的节点
	public Node get(int index){
//		Node node;
		if(index<0||index>=size){
			return null;
		}
		else{
			Node tnode = root;
			for(int i=0;i<index;i++){
				tnode = tnode.getNext();
			}
			return tnode;
		}
	}
//返回链表的长度
	public int getsize(){
		return size;
	}
//在指索引位置插入对象
	public void add(int index,Object obj){
		//实例化一个新的节点对象
		Node newnode =new Node(obj);
		if(index==0){
			root.setPrivous(newnode);
			newnode.setNext(root);
			root = newnode;
			size++;
		}
		else if(index==size){
			last.setNext(newnode);
			newnode.setPrivous(newnode);
			last = newnode;
			size++;
		}
		else if(index<0||index>size){
			System.out.println("您输入的索引位置越界了！！！");
		}
		else{
			//得到当前位置的节点对象
			Node node = this.get(index);
			//得到该节点的父节点
			Node pnode = node.getPrivous();
			//设置父节点的下一个节点为要添加的节点
			pnode.setNext(newnode);
			newnode.setPrivous(pnode);
			node.setPrivous(newnode);
			newnode.setNext(node);
			size++;
		}
	}
//	删除索引位置处的节点
	public void delete(int index){
		Node node = this.get(index);
		Node pnode = node.getPrivous();
		Node nnode = node.getNext();
		if(pnode==null){
			root = nnode;
		}
		else if(nnode==null){
			pnode.setNext(null);
		}
		else{
		pnode.setNext(nnode);
		nnode.setPrivous(pnode);
		}
		size--;
	}
//  删除指定的节点	
	public void delete(Object obj){
		Node node = new Node(obj);
		for(int i=0;i<this.getsize();i++){
			if(this.get(i)==node){
				Node nownode = this.get(i);
				Node pnode = nownode.getPrivous();
				Node nnode = nownode.getNext();
				if(i==0){
					root=nnode;
				}
				else if(i==this.getsize()){
					pnode.setNext(null);
				}
				else{
					pnode.setNext(nnode);
					nnode.setPrivous(pnode);
				}
				size--;
			}
		}
		System.out.println("您删除了"+obj);
	}
//	链表排序
	public  void sort(){
		for(int i=0;i<this.getsize();i++){
			for(int j=i;j<this.getsize();j++){
				Node node1 = this.get(i); 
				Node node2 = this.get(j);
				Object date_1 = node1.getDate();
				Object date_2 = node2.getDate();
				int date1 = (int) node1.getDate();
				int date2 = (int) node2.getDate();
				if(date1>date2){
					node1.setDate(date_2);
					node2.setDate(date_1);
				}
			}
		}
	}//end sort
	
	
	
}

主函数：

import java.util.Random;

public class Manager {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		LinkedList ll = new LinkedList();
		Node node = null;
		Random ran = new Random();
		for(int i=0;i<20;i++){
			node = new Node();
			node.setDate(ran.nextInt(50));
			ll.add(node);
		}
		
		//在指定位置添加一个节点
		ll.add(5, 111);
		//越界添加
//		ll.add(25,25);
//		//删除指定索引位置的节点
//		ll.delete(1);
//		//删除指定的节点
//		ll.delete(10);
		
		System.out.println("排序前~~~~~~~~~~");
		for(int i=0;i<ll.getsize();i++){
			node = ll.get(i);
			System.out.println(node.getDate());
		}
		
		
		System.out.println("排序后~~~~~~~~~~");
		//给链表排序
		ll.sort();
		
		for(int i=0;i<ll.getsize();i++){
			node = ll.get(i);
			System.out.println(node.getDate());
		}
		
	}

	
	
}