Java数据结构之双端链表原理与实现方法

本文实例讲述了Java数据结构之双端链表原理与实现方法。分享给大家供大家参考，具体如下：

一、概述：

1、什么时双端链表：

链表中保持这对最后一个连点引用的链表

2、从头部插入

要对链表进行判断，如果为空则设置尾节点为新添加的节点

3、从尾部进行插入

如果链表为空，则直接设置头节点为新添加的节点，否则设置尾节点的后一个节点为新添加的节点

4、从头部删除

判断节点是否有下个节点，如果没有则设置节点为null

二、具体实现

/**
 * @描述     头尾相接的链表
 * @项目名称   Java_DataStruct
 * @包名     com.struct.linklist
 * @类名     LinkList
 * @author   chenlin
 * @date    2010年6月26日 上午8:00:28
 * @version   1.0
 */
public class FirstLastLinkList {
  //头
  private Node first;
  //尾
  private Node last;
  public FirstLastLinkList(){
    first = null;
    last = null;
  }
  /**
   * 插入数据
   * @param value
   */
  public void insertFirst(long value){
    Node newNode = new Node(value);
    if (first == null) {
      last = newNode;
    }else {
      //把first节点往下移动
      newNode.next = first;
    }
    //把插入的节点作为新的节点
    first = newNode;
  }
  /**
   * 插入数据
   * @param value
   */
  public void insertLast(long value){
    Node newNode = new Node(value);
    if (first == null) {
      first = newNode;
    }else {
      last.next = newNode;
    }
    //把最后个节点设置为最新的节点
    last = newNode;
  }
  public boolean isEmpty(){
    return first == null;
  }
  /**
   * 删除头节点
   * @param value
   * @return
   */
  public Node deleteFirst(){
    if (first == null) {
      throw new RuntimeException("链表数据不存在");
    }
    if (first.next == null) {
      last = null;
    }
    Node temp = first;
    first = temp.next;
    return temp;
  }
  public Node deleteByKey(long key){
    Node current = first;
    Node last = first;
    while(current.data != key){
      if (current.next == null) {
        System.out.println("没找到节点");
        return null;
      }
      last = current;
      current = current.next;
    }
    if (current == first) {
      //return deleteFirst();
      //指向下个就表示删除第一个
      first = first.next;
    }else {
      last.next = current.next;
    }
    return current;
  }
  /**
   * 显示所有的数据
   */
  public void display(){
    if (first == null) {
      //throw new RuntimeException("链表数据不存在");
      return;
    }
    Node current = first;
    while(current != null){
      current.display();
      current = current.next;
    }
    System.out.println("---------------");
  }
  /**
   * 查找节点1
   * @param value
   * @return
   */
  public Node findByValue(long value){
    Node current = first;
    while(current != null){
      if (current.data != value) {
        current = current.next;
      }else {
        break;
      }
    }
    if (current == null) {
      System.out.println("没找到");
      return null;
    }
    return current;
  }
  /**
   * 查找节点2
   *
   * @param key
   * @return
   */
  public Node findByKey(long key) {
    Node current = first;
    while (current.data != key) {
      if (current.next == null) {
        System.out.println("没找到");
        return null;
      }
      current = current.next;
    }
    return current;
  }
  /**
   * 根据索引查找对应的值
   * @param position
   * @return
   */
  public Node findByPosition(int position){
    Node current = first;
    //为什么是position - 1，因为要使用遍历，让current指向下一个， 所以position - 1的下个node就是要找的值
    for (int i = 0; i < position - 1 ; i++) {
      current = current.next;
    }
    return current;
  }
  public static void main(String[] args) {
    FirstLastLinkList linkList = new FirstLastLinkList();
    linkList.insertFirst(21);
    linkList.insertFirst(22);
    linkList.insertFirst(23);
    linkList.insertLast(24);
    linkList.insertLast(25);
    linkList.insertLast(26);
    linkList.insertLast(27);
    linkList.display();
    System.out.println("---查找-------------------------------------");
    linkList.findByKey(25).display();
    System.out.println("--删除first-------------------------------------");
    //linkList.deleteFirst().display();
    ///linkList.deleteFirst().display();
    //linkList.deleteFirst().display();
    //linkList.deleteFirst().display();
    System.out.println("-删除指定值---------------------------------------");
    linkList.deleteByKey(27).display();
    linkList.deleteByKey(21).display();
    System.out.println("----------------------------------------");
    linkList.display();
  }
}

更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。