链表小结

1、链表的构成：包括节点类(Node)、根节点(root)、末节点(tail)、其中节点类包括data和next两个属性。

2、链表内部的一些构造方法和方法：添加(add)、得到长度(size)、得到指定位置的储存内容(get)、移除(remove)和插入(insert)。

3、链表的作用：个人对链表还不是很熟悉，但是感觉它有一个突破点——那就是它把原来动态分配的空间连接在了一起，方便了管理。而且他的大小是随意改变的，不像数组之类的在初始化时就已经确定了大小。

4、图示解说：

 

public class LHWLink {
	//定义一个根节点
	private Node root;
	//定义一个末尾的节点
	private Node last;
	//定义一个长度
	private int size;
	
	//定义一个添加的方法
	public void add(Object ob){
		//定义一个新节点
		Node node = new Node();
		node.data = ob;
		if(root == null){
			root = node;
			last = node;
		}else{
			last.next = node;
			last = node;
		}
		size++;
	}
	//定义一个的得到长度的方法
	public int size(){
		return size;
	}
	//定义一个得到的方法
	public Object get(int index){
		if(index<0 || index>size-1){
			//抛出一个异常
			throw new java.lang.ArrayIndexOutOfBoundsException("超出范围");
		}else{
			Node temp = root;
			if(index == 0){
				return root.data;
			}
			for(int i=0;i<index;i++){
				temp = temp.next;
			}
			return temp.data; 
			
		}
	}
	//定义一个删除的方法
	public Object remove(int index){
		if(index<0 || index>size-1){
			//抛出一个异常
			throw new java.lang.ArrayIndexOutOfBoundsException("超出范围");
		}else{
			if(size == 1){
				size--;
				Object obj = root.data;
				root = null;
				return obj;
			}
			size--;
			if(index == 0){
				Object obj = root.data;
				root = root.next;
				return obj;
			}
			Node temp = root;
			for(int i=0;i<index-1;i++){
				temp = temp.next;
			}
			Object dele_data = temp.next.data;
			temp.next = temp.next.next;
			if(index == size){
				last = temp;
			}
			return dele_data;
		}
		
	}
	//定义一个插入的方法
	public void insert(Object obj, int index){
		if(index<0 || index>size-1){
			//抛出一个异常
			throw new java.lang.ArrayIndexOutOfBoundsException("超出范围!");
		}else{
			Node temp = root;
			Node node = new Node();
			node.data = obj;
			if(index == 0){
				node.next = root;
				root = node;
				size++;
				return;
			}
			for(int i=0;i<index-1;i++){
				temp = temp.next;
			}
			node.next = temp.next;
			temp.next = node;
			size++;
		}
		
	}

}

 节点类

 

 

public class Node {
	public Node next;
	public Object data;
//	public Node front;(如果要建立双向链表)
}

 

 

评论

1 楼 ayaome 2014-03-25  

美术功底不咋的