简单链表

 

链表总结

 

概念：

  1.链表是一种物理存储单元上非连续，非顺序的储存结构。它有多个结点组成，一个结点包括存储数据的数据区域和指向下一个结点的指针域。

  2.链表一般会有普通链表，循环链表，双向链表的分类。

 

构建结点：

 

public class Node {
	//要存储的数据
	private Object data;
	//节点的孩子节点
	private Node child;
}

 

 

  这样即构建好了一个结点，date为任意类型的数据，child即为指向下一个结点的指针，当然，数据类型也可以写多个，可以一个结点储存多个信息。

  之后写入获取和设置函数，方便改变和得到结点的内容

 

建造链表

  链表是一个灵活的容器，可以储存任意类型的数据，并且因为数据物理内储存不连续，所以对于删除和插入操作比较容易。

 

  public class LinkTest {
	private Node root=null;  //根节点
	private Node end=null;	//尾结点
	private int length=0; 	//长度
}

 

 

  这样创造一个空链表，对于链表，应该具有基本的添加函数，删除函数，获取函数。

//添加结点
	public void add(Node node) {
		//如果链表为空
		if(null==root){
			root = node;
			end = node;
		}
		else {//如果不为空
			node.setChild(null);
			end.setChild(node);
			node.setParent(end);
			end = node;
		}
		this.length++;
	}
	//获取结点数据
	public Object getNodeData(int index){
		//设计指针 并指向头结点
		Node temp = new Node("指针");
		temp = root;
		//根据索引找到药修改的位置
		for(int i=0;i<index;i++){
			temp = temp.getChild();
		}
		return temp.getData();
	}
	//移除一个结点
	public void remove(int index){
		if(index<0||index>length){
			return ;
		}
		Node temp = new Node("指针");
		temp =root;
		//利用循环找到要删除的节点索引位置
		for(int i=0;i<index-1;i++){
			temp = temp.getChild();
		}
		//删除该结点
		temp.setChild(temp.getChild().getChild());
		//防止尾结点被删除儿导致的 空指针
		if(null!=temp.getChild())
		temp.getChild().setParent(temp);
		//移除后队列长度减一
		this.length--;
	}

 

  其实除了这些操作外，还可以自己随意定义很多操作，所以链表是一个很灵活的容器，实现自定义队列等等操作。

 

  值得注意的是：在对结点之间经行关系的建立时，一定不要使链表某一部分先断掉，否则那一部分将会消失。如在经行添加操作时,必须先建立“添加结点”与后一个结点的关系，在将前一个结点与“添加结点”建立关系。如果反着来，则会使后面的结点与之前的结点失去联系，从而断掉，public void add(Node node,int i){

//如果链表为空
		if(null==root){
			root = node;
			end = node;
		}
		else{
			//建立指针，为了不使头结点断掉，新建指针代替头结点去寻找位置
			Node temp = new Node("指针");
			temp = root;
			//找到要出入的位置
			for(int j=0;j<i;j++){
				temp = temp.getChild();
			}
			node.setChild(temp.getChild());
			temp.setChild(node);
		}
	}

 

其中node.setChild(temp.getChild());

temp.setChild(node);不能调换位置。