链表——双端链

链表——双端链表：

 

双端链表和单向列表时相似的，但是在单向列表的基础上增加了一个特性，就是增加了对最后一个
链接点的引用，就像对第一个链接点的引用一样。但我们试图寻找最后一个链接点的时候就不用像
单向链表需要遍历所有的链接点了，可以直接通过最后一个链接的位置获取数据，并且可以在链表的
尾端添加节点。

 

 

//双端列表
class FirstLastList{
 
 public static void main(String[] args) {
  FirstLastList f = new FirstLastList();
  f.insertFirst(3, 3);
  f.insertFirst(4, 4);
  f.insertLast(1, 1);
  f.insertLast(2, 2);
  f.disPlay();
  System.out.println("delete-------------");
  f.deleteFirst();
  f.disPlay();
 }
 
 //记录第一个链接点地址
 public Link first;
 //记录最后一个链接点地址
 public Link last;
 
 //初始化
 public FirstLastList(){
  first = null;
  last = null;
 }
 
 //判断是否为空
 public boolean isEmpty(){
  return first == null;
 }
 
 //添加第一个链接点，这里和单向链表相识，不同的是当链表为空时，必须制定
 //最后一个链接点的地址，否则就无法直接访问末尾的链接点，也就无法在链表尾部添加链接点。
 public void insertFirst(int i, double d){
  Link newLink = new Link(i,d);
  
  //如果为空初始化末端链接点。此时，第一个链接点也就是最后一个链接点。
  if(isEmpty()){
   last = newLink;
  }
  //此处和单向一样，添加首个链接点，将节点的next指向当前的first
  newLink.next = first;
  //首个链接点指向新增加的链接点
  first = newLink;
 }
  
 //增加末尾链接点，末尾添加的方向和添加首个链接点的方向相反。
 public void insertLast(int i, double d){
  Link newLink = new Link(i,d);
  
  //如果为空，初始化首个链接点
  if(isEmpty()){
   first = newLink;
  }else{
   //此处和添加首节点不同，必须是不为空的时候才能操作，
   //此处操作的末链接点的next.
   last.next = newLink;
  }
  //更新末尾链接点地址
  last = newLink;
 }
 
 //删除首节点
 public void deleteFirst(){
  if(isEmpty()){
   System.out.println("list is null");
  }else{
   //如果首节点的下一个链接点为空，就将last置空
   if(first.next == null){
    last  = null;
   }
   //变更首节点的位置。
   first = first.next;
  }
 }
 
 public void disPlay(){
  Link current = first;
  while(current!=null){
   System.out.println(current.dData);
   current = current.next;
  }
 }
}

//链接点对象
class Link{
 public int iData;
 public double dData;
 
 //关系子段，用于存储下一个链接点的位置
 public Link next;
 public Link(int id, double dd){
  this.iData = id;
  this.dData = dd;
 }
 public void displayLink(){
  System.out.println("{" + iData + "," + dData + "}");
 }
}