链表 插入删除添加

                                                         Java中的链表

              我在写关于java代码的过程中，总要引用C中的术语，并不是因为卖弄C中的学识，而是作为一种最为基础的语言，它的最先存在必定是有意义的，毕竟C++，C#，java都是以它为基础慢慢建立起来的，所以在链表这里我一如往常引用C中的指针来解释。首先插入一段代码：

public class Data {
	Data next;//定义节点,其实在这里节点的概念最难理解，我的理解是开辟一个对象空间一个框，用于指针（C术语）来获取到节点，来接受外来位置
    Object data;//定义元素

}

 这里的关键是next应用，它在C语言中是指针的应用，但是我们都知道Java中并没有指针，所以我们解释成引用，它用来保存当前节点的地址和指向下一个节点。Object data  由于无法知道将要插入元素的类型，所以定义为Object

一下的难点是插入实现，它涉及到前节点和后节点，图示会清楚一些：

 

 

public class Link {
 private Data root;//定义表头
 private Data tail;//定义表尾
 private int size;//定义长度
 public static void main(String args[]){
  Link link=new Link();
  for(int i=0; i<10; i++){
   link.add("str"+i);
  }
 // System.out.println("删除的元素是："+link.remove(9));
  //System.out.println("删除的元素是:"+link.remove(0));
  link.insert(0,"a");
  link.insert(2, "b");
  for(int i=0; i<link.getsize(); i++){
   System.out.println(link.get(i));
  }
  System.out.println("===========================");
  //link.add("add");
  for(int i=0; i<link.getsize(); i++){
   System.out.println(link.get(i));
  }

 }
 //定义将要添加到链表的元素
 public void add(Object data){
  Data node=new Data();//创建数据对象
     node.data=data;//接受传入数据
     //如果表头为0，也就是链表为空
  if(root==null){
   root=node;//将将要加入的节点位置赋给表头
   tail=node;//同理，表尾的位置也是新加入元素位置
  }
  //如果链表不为空
  else{
   tail.next=node;//将链表尾部下一个位置指向node的地址
   tail=node;//因为表尾永远指向表尾，所以将表尾指向node节点的位置
  }
   size++;//长度+1
 }
 //查找指定位置的元素
 public Object get(int index){
  //判断越界情况
  if(index<0||index>=size){
   throw new java.lang.ArrayIndexOutOfBoundsException("超出队列范围！");

  }
  //定义一个temp值来接受表头，具体作用下面代码诠释
  Data temp=root;
  //遍历不断指向下一个节点
  for(int i=0;i<index;i++){
   temp=temp.next;
   
  }
  
  
  
  return temp.data;
  
 }
 public boolean insert(int index,Object a){
  Data node=new Data();//创建数据对象
     node.data=a;//接受传入数据
  if(index < 0 || index >= size){
   //抛出一个异常
   throw new java.lang.ArrayIndexOutOfBoundsException("超出队列范围！");
  }
  //表头添加方法
  if(index==0){
   //将当前节点指针指向根节点，相当于插入，形象理解为鼠标插入电脑，next就是那根线
   node.next=root;
   //因为根节点总是指向表头，所以将根节点指向表头
   root=node;
   //长度+1
   size++; 
   return true;
  }
  //定义一个节点来接受根节点
  Data temp=root;
  //遍历循环来查找将要插入元素的前一个节点
  for(int i=0;i<index-1;i++){
   //循环查找
   temp=temp.next;
  }
  //定义一个节点来存储将要插入元素的下一个节点
  Data temp1=temp.next;
  //将插入元素的上一个节点指针指向当前节点，相当于连接
  temp.next=node;
  //将当前节点的指针指向将要插入元素位置的下一个节点
  node.next=temp1;
  //长度+1
  size++;

  
  return true;
 }
 public Object remove(int index){
  if(index < 0 || index >= size){
   //抛出一个异常
   throw new java.lang.ArrayIndexOutOfBoundsException("超出队列范围！");
  }
  //当长度为1时具体处理，理由是不走for循环
  if(size == 1){
   size--;
   Object obj = root.data;//定义一个对象接收data
   root = null;//清空
   return obj;
  }
  size--;
  //理由同上
  if(index == 0){
   Object obj = root.data;
   root = root.next;
   return obj;
  }
  //遍历循环寻找要删除的元素的前一个结点，
  Data  temp = root;
  for(int i=0; i< index-1;i++){
   temp = temp.next;
  }
  Object obj = temp.next.data;//将下一个节点的数据赋给obj，也就是将要删除的元素
  temp.next = temp.next.next;//跳过此结点，也就是结点存储下下节点的位置
  //节点尾部的处理
  if(index == size){
   tail = temp;
  }
  return obj;
 }
    //返回链表长度
 public int getsize(){
  return size;
 }

}
出来的结果大致上是：

 

 

评论

1 楼 ayaome 2014-03-21  

图文并茂，good！只是Data类的取名乖乖的