单向链表

链表：一个纠结的问题。感觉跟学异常的时候的感觉一样，知道有这回事，知道怎么操作，却还是有种不详的感觉。在学校简单接触过，被它打败了。

 

package cn415;

public class List<E> {

	
	private  static  class  Node<E>{
		E  e;
		Node  next;
		//构造函数
		public  Node(E e,Node  next){
			this.e=e;
			this.next=next;
		}
	}
	
	//定义一个头节点
	private Node<E>  head;
	//定义链表大小
	private  int size=0;
	
	//清空链表
	public  void  clear(){
		head=null;
	}

	
	//添加头节点数据    私有的方法 相对外部是不可见的定义为private
	private  void  addFirst(E e){
		//封装成节点
		 head=new Node<E>(e,null);
		 size++;
	}
	
	//头结点前插入节点数据
	public  void  addHead(E e){
		if(size==0){
			this.addFirst(e);
		}else{
		//封装成节点
		Node<E>  newNode=new Node<E>(e,head);
		//newNode指向head
		head=newNode;
		size++;
		}
	}
	//向末尾添加节点数据
	public  void  addLast(E e){
		this.insert(e, size+1);
	}

	//插入数据到指定位置的结点中
	public void insert(E e,int index){
		if(index<1||index>size+1){
			System.out.println("插入时输入有误！！");
		}
		if(index==1){
			this.addHead(e);
		}else{
			int count=1;
			for(Node<E> p=head;p!=null;p=p.next){
				if(count+1==index){
					Node<E> newNode=new Node<E>(e,p.next);
					p.next=newNode;
					size++;
					return;
				}
				count++;
			}
		}
	}
	
	
	//取得指定位置的结点
	public  Node<E> getIndex(int index){
		int  count=1;
		Node<E>  node=null;
		//遍历
		for(Node<E> tem=head;tem!=null;tem=tem.next){
			if(count==index){
				node=tem;
				break;
			}
			count++;
		}
		return node;
	}
	
	//删除头结点
	public void  delateHead(){
		head=head.next;
		size--;
	}
	
	//删除指定位置的结点数据
	public void delate(int index){
		if(index<1||index>size+1){
			System.out.println("删除时输入有误！！！");
		}else if(index==1){
			this.delateHead();
		}else{
			//取得指定位置的结点
			Node<E> node=this.getIndex(index);
			//取得指定位置前的一个结点
			Node<E> lastnode=this.getIndex(index-1);
			//修改前一个结点的next
			lastnode.next=node.next;
			//大小改变
			size--;
		}
		
	}
	
	
	//打印所有节点数据的方法
	public  void  print(){
             Node<E>  tem=head;
             for(int i=1;i<=size;i++){
            	 System.out.println("第"+i+"节点是"+"\t"+tem.e);
            	 tem=tem.next;
             }
	}
	//取得链表大小
	public int getSize() {
		return size;
	}
	public static void main(String[] args) {
              
		List<String>  list=new List<String>();
		list.addFirst("王力宏");
		list.addHead("周杰伦");
		list.addHead("林俊杰");
		list.addHead("林秋离");
		System.out.println("指定位置"+"   "+5+"   "+"插入测试"+"\t"+"*******************");
		list.insert("cuole", 5);
		list.print();
		System.out.println("末尾添加测试"+"\t"+"*******************");
		list.addLast("中南大学");
		list.print();
		System.out.println("头部删除测试"+"\t"+"*******************");
		list.delateHead();
		list.print();
		System.out.println("指定取得测试"+"\t"+"*******************");
		System.out.println("指定结点"+"   "+4+"   "+"取得数据测试的结果是"+list.getIndex(4).e);
		System.out.println("指定删除测试"+"\t"+"*******************");
		list.delate(5);
		list.print();
		
		
		
	}

}

 

打印的结果是 ：

指定位置   5   插入测试 *******************
第1节点是 林秋离
第2节点是 林俊杰
第3节点是 周杰伦
第4节点是 王力宏
第5节点是 cuole
末尾添加测试 *******************
第1节点是 林秋离
第2节点是 林俊杰
第3节点是 周杰伦
第4节点是 王力宏
第5节点是 cuole
第6节点是 中南大学
头部删除测试 *******************
第1节点是 林俊杰
第2节点是 周杰伦
第3节点是 王力宏
第4节点是 cuole
第5节点是 中南大学
指定取得测试 *******************
指定结点   4   取得数据测试的结果是cuole
指定删除测试 *******************
第1节点是 林俊杰
第2节点是 周杰伦
第3节点是 王力宏
第4节点是 cuole