数据链表

 

链表

 

在链表中，逻辑顺序是通过指针实现的。

链表中第一个结点称为根节点，最后一个结点称为尾结点。

在单链表中，一个结点（链表是由一系列的结点组成的）有一个指向下一节点的指针（尾结点除外）。

在双链表中，一个结点有两个指针，一个指向上一节点，一个指向下一节点（首尾结点只有一个指针，另一指针指向为null）。

在循环链表中，根尾结点也都有两个指针，比双链表多出来的那个指针使得根节点的上一节点是尾结点，也使得尾结点的下一结点是根节点，这样整串链表组成了一个首尾相连的环形。

 

链表由一个个的结点组成，结点在内存中开辟的空间又分为两部分，一部分用来存储数据（数据域），另一部分用来存储指针（引用域）。（在单链表中，尾结点的指针指向null）

 

创建一个链表的流程如下：

创建Node 结点类

/**定义一个节点类
 * @param args
 */
public class Node {

	private Object ob;//存储内容
	private Node next;//下一个结点
	private Node pre;//上一个结点
	/*
	 * 定义为结点添加数据对象的方法
	 */
	public void add(Object ob){
		this.ob=ob;
	}
	/*
	 * 定义得到数据对象的方法
	 */
	public Object getob(){
		return ob;
	}
	/*
	 * 定义得到下一个结点的方法
	 */
	public Node getNext() {
		return next;
	}
	/*
	 * 定义添加下一个结点的方法
	 */
	public void setNext(Node next) {
		this.next = next;
	}
	
	/*
	 * 定义得到上一个结点的方法
	 */
	public Node getPre() {
		return pre;
	}

	/*
	 * 定义添加上一个结点的方法
	 */
	public void setPre(Node pre) {
		this.pre = pre;
	}
}

在创建一个链表类chain

public class Chain {
	
	private Node root;//根结点
	private Node tail;//尾结点
	private int size=0;//链表中结点个数
	
	/*
	 * 定义添加结点的方法
	 */
	public void add(Object ob){
		Node node=new Node();
		node.add(ob);
		if(getsize()==0){
			root=node;
			tail=root;
			tail.setPre(null);
		}
		else{
			tail.setNext(node);
			node.setPre(tail);
			tail=node;
		}
	
		size++;
		
	}
	/*
	 * 定义删除结点的方法,根据索引数
	 */
	public void delete(int index){
		Node temp=root;
		if(index<0||index>=size){
			System.out.println("索引越界！");
		}
		else{
			if(index==0){
				root=temp.getNext();
			}
			else{
				if(index==size-1){
					tail=tail.getPre();
				}
				else{
					//temp 是要被删除的那个结点
					temp=getnode(index);
					//找到temp的前一个结点
					Node fnode=temp.getPre();
					System.out.println("dddd"+ fnode.getob());
					//找到temp的后一个结点
					Node nnode=temp.getNext();
					//让前一个和后一个结点双向联系
					fnode.setNext(nnode);
					nnode.setPre(fnode);
//					System.out.println(temp.getob()+"..");
				}
			}
			size--;
		}
	}
	/*
	 * 定义得到结点的方法
	 */
	public Node getnode(int index){
		Node gnode=root;
		if(index<size&&index>=0){
			if(index==0){
				gnode=root;
			}
			else{
				for(int i=0;i<index;i++){
					gnode=gnode.getNext();
				}
			}
			return gnode;
		}
		else
			return null;
	}
	/*
	 * 定义得到链表结点数量size的方法
	 */
	public int getsize(){
		return size;
	}
}

使用队列和链表可以很方便的添加新内容或者删除内容，可以对数量较大的信息进行简单编辑。