Java中单链表之浅析

       何谓链表？百度下可以知道链表是一种物理存储上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

       以我的理解，我们可以这样看：其中的每一个结点就是一个加锁的盒子，盒子里面有一把装着另一个盒子的钥匙（通过钥匙能找到并打开盒子），那个盒子被附上next的标志；盒子里还装着本身拥有的物品即数据data；由这么多一系列盒子组成的就是链表，我们可以通过每一个盒子找到相应下一个盒子，然后反复······此外，最前面的盒子和最后面的盒子被贴上root和end的标签，即表头和表尾，而且规定凡是被贴上这两类标签的盒子不加锁！！如此我们便能通过表头和表尾的盒子寻找到其他所有的盒子了。当然这个比喻是对单链表而言啦，至于其他链表，我们可以类推下去。

     既然谈到链表是由一系列结点组成的，那我们首先自然得创建一个结点类哈:

public class Node<E> {
   
	public Node<E> next;  //定义节点后一个节点
	public Node<E> forward;//定义节点前一个节点
	public Object data;//定义节点储存的数据
}

 然后得创建一个链表类，其中要有如下属性;节点类型的root（根结点）和end（尾结点）还有整型的size（链表长度）。接着我们就写其中几种方法:

 

      1.向表尾添加数据                                    2.删除指定位置的数据

      3.向指定位置删除数据                             4.获取指定位置的数据

      5.获取链表长度

public class Link<E> {
   
	private Node<E> root;//创建根节点
	private Node<E> end;//创建尾部节点
	private int size;//创建链表长度变量
	
	public void add(Object obj)
	{
		Node<E> node=new Node<E>();//创建一个对象
		node.data=obj;//将添加的内容赋给节点
		//如果根节点为空
		if(root==null)
		{
			root=node;//创建的节点地址传给根节点地址
			end=node;//创建的节点地址传给尾节点地址
		}
		else{
			end.next=node;//创建的节点地址传给尾节点内的节点
			end=node;//把创建的节点作为尾节点
			
		}
		size++;
	}
	//删除指定位置上的数据
	public Object remove(int index)
	{
		
		if(index<0||index>size)
		{
			throw new java.lang.ArrayIndexOutOfBoundsException("索引位置超出队列范围");
		}
		//如果队列只有一个数据
		if(size==1)
		{   size--;
			Object obj=root.data;
			root=null;
			return obj;
		}
		
		//如果索引为0
		if(index==0)
		{
			Object obj=root.data;
			root=root.next;
			return obj;
			
		}
		//创建临时节点，使其不断被赋成此后节点的值，相当于指针
		Node<E> temp=root;
		for(int i=0;i<index-1;i++)
		{
			temp=temp.next;
		}
		Object obj=temp.next.data;
		temp.next=temp.next.next;
		//如果索引指向最后一个节点，则
		if(index==size-1)
		{
			end=temp;
		}
		size--;
        return obj;		
        
	}
	//向指定位置插入数据
	public void insert(Object obj,int index)
	{
		Node<E> node=new Node<E>();
		node.data=obj;
		
		 if(index<0||index>size)
		   {
			 //如果索引超出索引范围
			   throw new java.lang.ArrayIndexOutOfBoundsException("索引超出队列范围！！！");//抛出异常
		   }
		 
		size++;
		
		if(index==0)
		{
           //插到表头
			
			node.next=root;
			root=node;			
			
		}
		else{
		//创建临时节点，用于访问各个节点
		Node<E> temp=root;
		for(int i=0;i<index-1;i++)
		{
			temp=temp.next;
		}
		node.next=temp.next;
		temp.next=node;
		

		}
	}
	 //查找指定位置上的数据
	public Object get(int index)
	{
	   if(index<0||index>size)
	   {
		 //如果索引超出索引范围
		   throw new java.lang.ArrayIndexOutOfBoundsException("索引超出队列范围！！！");//抛出异常
	   }
	   	   Node<E> temp=root;
		   for(int i=0;i<index;i++)
		   {
			   temp=temp.next;
		   }
		   return temp.data;
	   
	}
	//获得队列长度
	public int size()
	{
		return size;
	}
	

}

  其中我们可以发现有出现下面的代码：

 

if(index<0||index>size)
	   {
		 //如果索引超出索引范围
		   throw new java.lang.ArrayIndexOutOfBoundsException("索引超出队列范围！！！");//抛出异常
	   }

 当索引位置超出链表长度内的范围，我们自然实现不了，但是系统不会报错。为了提示出错，我们要调用java中的异常类发出警告！！

 

为了让大家更清楚了解其中几种方法的原理，现配图如下：

 

1)这是插入新结点的原理：让新结点指向索引位置前一个结点的next，然后索引位置后一个结点指向新结点的next，这样便能实现了！

2）删除指定位置的结点原理：让指定位置结点后一个结点直接指向指定位置结点前一个结点的next，这样就能越过指定位置的结点而直接寻找后面的结点了！


 
 接下来我们再创建一个实现类，就能利用所创建的链表了：

public class MyLink extends Link {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
         MyLink ml=new MyLink();//实例化对象
         for(int i=0;i<8;i++)
         {
        	 ml.add(i);
         }
        ml.printLink(ml);
        System.out.println("");
        System.out.println("删除的数据为："+ml.remove(7));
        ml.insert(3, 0);
        ml.insert(5, 4);
        ml.printLink(ml);
         
	}
	/*
	 * 打印队列的方法
	 */
    public void printLink(MyLink ml)
    {
    	 for(int i=0;i<ml.size();i++)
         {
        	 System.out.print(ml.get(i));
         }
    }
}

 

 

评论

2 楼 ayaome 2014-03-23  

使用泛型后Obejct就可以用E代替了

1 楼 ayaome 2014-03-23