链表小结

                          链表（线性链表）

现在我们开始学习数据结构了，数据结构到底是什么，从名称上讲，应该是数据在计算机内部的存储方法。不过，这只是个概念而已，都说重要的还是要了解内涵。

 链表是一种常见的基础数据结构，是一种物理存储单元上非连续，非线性的存储结构，数据元素的逻辑顺序是通过链表中 的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点包括两个域，其中存储数据元素信息的域称为数据域，存储其他结点的存储位置的域称为指针域。

现在我暂时还不清楚链表到底是一种线性的，还是非线性的。找了下资料，问了同学说法不一，我也完全不清楚。。。所以，只能做暂时的小结。

线性链表有：单链表，双向链表，循环链表。

顺序存储结构和这种链式存储结构还是有很大差异的。前者可以随机存储表中的任一元素，但是一涉及到插入或删除操作就比较麻烦了。而后者刚好方便的能解决那个插入或删除的问题，不过它又不能随机获取元素，因为它是没有下标的。

简单介绍下单链表的创建，元素添加，删除，更新

首先链表是有一系列结点链接而成的，所以，首先要定义这样一个需要的结点类，它包括两个属性（一个基本数据类型，一个结点类型），这里用链表来实现队列 

1. 结点有了，就可以创建链表队列了，其实创建链表的过程也可以是不断添加元素的过程。

public void add(LinkNode node){

       //判断此时的根结点是否为 空

       if(root==null){  //若为空，则将新的元素作为根结点

           root=node;

           end=root;

       }else {       //若不为空，则添加在队列的末尾

           end.setNext(node);

           end=node;

       }

    }

 

 

 

 

 

 

 

 

 

这个也主要是判断是否加入的是第一个结点，是的话就将它设为根结点，不是的话就在原来链表的末尾添加就行了。 

2.有了链表队列，就可以计算它的长度，计算长度其实也就是遍历这个链表的过程，用一个计数器就可以完成。也可以根据索引来获取元素，原理和求长度是一样的。

 

/**
	 * 计算队列的长度
	 * @return
	 */
	public int size(){
		int count=0;
		Object obj=root.getObj();
		if(obj==null){
			return 0;
		}else{
			count++;
			LinkNode node=root.getNext();
			while(node!=null){
				count++;
				node=node.getNext();
			}
		}
		return count;
	}
	/**
	 * 任意获取队列中的元素
	 * @param index 要查找元素的下标
	 * @return
	 */
	public Object get(int index){
		int count=0;   //定义一个计数器
		//判断所提供的下标是否符合要求
		if(index>=this.size()||index<0){   //若不符，则报异常
		    throw new RuntimeException(""+index);  
		}else{ //若符合要求
			if(index==0){ //判断是否是 头结点
				return  root.getObj();
			}
			else { 
				LinkNode node=root.getNext();
				while(node!=null){
					count++;
					if(count==index){
						return  node.getObj();
					}
					else node=node.getNext();
				}
			}
		}
		return null;
	}

 

 

 

3.这个插入的过程就有点不一样了，这个也是和顺序表不同的地方。只要找到要插入的位置就可以将新的元素顺利的入队。这里只要修改下某些结点的前后继关系就好。这里还要注意的是看要插入的位置是否是第一个结点处。因为这样是要修改头结点的，其他位置上的操作都是一样的。

 

/**

     * 向已知的队列中插入新的元素

     * @param Node 待插入的元素

     */

    public  void insert(LinkNode node1,int index){

       int count=0;   //定义一个计数器

       //判断所提供的下标是否符合要求

       if(index>=this.size()||index<0){   //若不符，则报异常

           throw new RuntimeException(""+index);  

       }else{ //若符合要求

           if(index==0){ //判断是否是 插在队列的头

             node1.setNext(root);

             root=node1;

           }

           if(index==1){ //判断是否是插在下标为1的位置上

              node1.setNext(root.getNext());

              root.setNext( node1);

           }

           else { 

              count++;

               LinkNode  node=root.getNext(); 

              while(count<index){

                  if(count==index-1){

                     LinkNode node2=node.getNext();//获取指定为位置前一个的元素

                      node.setNext(node1);       //将新的元素作为指定位置前一个的直接后继

                      node1.setNext(node2);     //将新元素的后继赋值为指定位置的元素

                  }

                  node=node.getNext();

                  count++;

              }

           }

       }

    }

 

4.删除操作也有一个和插入类似的问题就是被删除结点是第一个结点。这种情况只需使root的指向第二个结点。若被删结点不是第一个结点，这种情况使被删结点的前一结点指向被删结点的后一结点可以了

/**

     * 在已知的队列中删除指定位置的元素

     * @param index  指定的位置

     */

    public void delete(int index){

       int count=0;   //定义一个计数器

       //判断所提供的下标是否符合要求

       if(index>=this.size()||index<0){   //若不符，则报异常

           throw new RuntimeException(""+index);  

       }else{ //若符合要求

           if(index==0){ //判断是否删除头结点

              root=root.getNext();
   }
                else if(index==1){ //判断是否是删除下标为1的元素

              LinkNode node=root.getNext();

              root.setNext(node.getNext());

           }

           else{

              count++;

               LinkNode  node=root.getNext(); 

              while(count<index){

                  if(count==index-1){ //找到要删除位置的前一个位置

                     LinkNode node1=node.getNext();//获得要删除位置上的元素

                     LinkNode node2=node1.getNext(); //获得要删除后一个位置的元素

                      node.setNext(node2);  //直接将指定的位置的前一个位置的后继修改为指定位置的后继

                  }

                  node=node.getNext();

                  count++;
              }

           }

       }

    } 

5.这个是修改指定位置的结点元素，找到要修改的前一个位置，将它的next设为要修改的那个，再将它的next修改为指定位置元素的原后继就可以了。

public void revamp(LinkNode  node1,int index){
		int count=0;   //定义一个计数器
		//判断所提供的下标是否符合要求
		if(index>=this.size()||index<0){   //若不符，则报异常
		    throw new RuntimeException(""+index);  
		}else{ //若符合要求
			if(index==0){ //判断是否是 插在队列的头
			  node1.setNext(root.getNext());
			  root=node1;
			}
			if(index==1){ //判断是否是插在下标为1的位置上
			   node1.setNext(root.getNext().getNext());
			   root.setNext( node1);
			}
			else { 
				count++;
			    LinkNode  node=root.getNext(); 
				while(count<index){
					if(count==index-1){
						node1.setNext(node.getNext().getNext());
						node.setNext(node1);  //直接将指定的位置的前一个位置的后继更换为要修改的
						
					}
					node=node.getNext();
					count++;
				}
			}
		}
	}

 这里主要简单的讲了下单链表，其实双向链表和循环链表跟这个也是非常类似的，只要稍作修改就可以完成了。