数据结构之链表

 

 public class LinkNode<E>{
	
	public E data;
	public LinkNode<E> next;


}

 

public class LinkList<E> {

	LinkNode<E> head;
	LinkNode<E> last;
	private int length;
	
	public void add(E obj){
		//新建一个节点对象
				LinkNode<E> node = new LinkNode<E>();
				//把要添加的数据挂在节点上
				node.data = obj;
				
				if(head == null){
					head = node;
					last = node;
				} else {
					//把新节点放在最后
					last.next = node;
					//把最后的节点指向新节点
					last = node;
				}
				length++;
	}
	
	public E get(int index){
		//判断是否超出范围
		if(index < 0 || index >= length){
			throw new java.lang.ArrayIndexOutOfBoundsException("超出范围");
		}
		//找到index位置的节点
		LinkNode<E> temp = head;
		for(int i=0; i<index;i++){
			temp = temp.next;
		}
		
		return temp.data;
	}

	
	
	public E remove(int index){
		//判断是否超出范围
		if(index < 0 || index >= length){
			throw new java.lang.ArrayIndexOutOfBoundsException("超出范围");
		}
		
		if(index == 0){
			length--;
			E data = head.data;
			head = head.next;
			return data;
		}
		
			
		//找到index位置的节点
		LinkNode<E> temp = head;
		//index对应节点的父节点
		LinkNode<E> prev = head;
		for(int i=0; i<index;i++){
			prev = temp;
			temp = temp.next;
		}
		prev.next = temp.next;
		
		if(index == length - 1){
			last = prev;
			System.out.println("last="+last.data);
		}
		length--;
		return temp.data;
	}
	
	
	public int size(){
		return length;
	}

}

 

链表公共单位   链结点代码

      

数组作为数据存储结构
无序数组中搜索是低效的   而在有序数组中是  插入又是低效的   而且在数组创建后它的大小就是不可改变的了

而运用链表  除非需要频繁通过下标随机访问各个数据  否则在很多使用数组的地方都可以用链表代替



如果要打比方的话

数组存储就好比  Bob住在贝克街16号  你只要在贝克街一路找下去就能找到


而链表则好比  Harry可能知道Bob在哪  Harry说他不知道但Jane 可能知道  Jane说她看到Bob和Peter一起出去了你打Peter的手机Peter说Bob和…….
链表内你无法通过直接地址访问数据项  必须使用数据的关系来定位它

 

单向链表

在链表中 每个数据项都被包含在“链结点”中  每个链结点都包含数据项和对下一个链结点的引用

包含一般数据结构的功能  增删查改

 

更多的链表结构还有双端链表  双向链表  有序链表  等等等等  待我之后慢慢写