Java实现无头双向链表操作

本文实例为大家分享了java实现无头双向链表的具体代码，供大家参考，具体内容如下

无头双向链表的结构：

代码分析

节点结构

class node {  private int data;  private node next;  private node prev;  public node(int data) {    this.data = data;    this.prev = null;    this.next = null;  }} private node head; // 头节点 private node last; // 尾节点 public doublelinked() {  this.head = null;  this.last = null;}

1. 头插法

/*** 1.头插法* @param data*/public void addfirst(int data) {  node node = new node(data);  if (this.head == null) {    this.head = node;    this.last = node;  } el {    node.next = this.head;    this.head.prev = node;    this.head = node;  }}

先判断链表是否为空，若为空，则直接插入，头节点和尾节点都直接指向新插入的元素；
若链表不为空，则把要插入节点的 next 指向链表头节点，头节点的 prev 指向新插入的节点，最后更新头节点为新插入节点，插入过程如下图所示：

2. 尾插法

/*** 2.尾插法* @param data*/public void addlast(int data) {  node node = new node(data);  if (this.head == null) {    this.head = node;    this.last = node;  } el {    this.last.next = node;    node.prev = this.last;    this.last = node;  }}

若链表为空，同头插法；
若链表不为空，则把链表尾节点的 next 指向要插入节点，要插入节点的 prev 指向链表尾节点，最后更新尾节点为新插入节点，插入过程如下图所示：

3. 查找是否包含关键字 key 在单链表中

// 查找  private node archindex(int index) {    checkindex(index);    int count = 0;    node cur = this.head;    while (count != index) {      cur = cur.next;      count++;    }    return cur;  }  // 合法性检查  private void checkindex(int index) {    if (index < 0 || index > getlength()) {      throw new indexoutofboundxception("下标不合法！");    }  }  /**  * 3.任意位置插入，第一个数据节点为0号下标  * @param index 插入位置  * @param data 插入的值  * @return true/fal  */  @override  public boolean addindex(int index, int data) {    if (index ==0) {      addfirst(data);      return true;    }    if (index == getlength()) {      addlast(data);      return true;    }    // cur 指向index位置的节点    node cur = archindex(index);    node node = new node(data);    node.next = cur;    cur.prev.next = node;    node.prev = cur.prev;    cur.prev = node;    return true;  }

4. 查找是否包含关键字 key 在单链表中

/*** 4.查找是否包含关键字 key 在单链表中* @param key 要查找的关键字* @return true/fal*/@overridepublic boolean contains(int key) {  node cur = this.head;  while (cur != null) {    if (cur.data == key) {      return true;    }    cur = cur.next;  }  return fal;}

5. 删除第一次出现关键字为 key 的节点

/*** 5.删除第一次出现关键字为 key 的节点* @param key* @return*/@overridepublic int remove(int key) {  node cur = this.head;  int olddata = 0;  while (cur != null) {    if (cur.data == key) {      olddata = cur.data;      // 头节点      if (cur == this.head) {        this.head = this.head.next;        this.head.prev = null;      } el {        // cur.next != null --->不是尾节点        if (cur.next != null) {          cur.next.prev = cur.prev;        } el {          this.last = cur.prev;        }      }      return olddata;    }    cur = cur.next;  }  return -1;}

6. 删除所有值为 key 的节点

/*** 6.删除所有值为 key 的节点* @param key*/@ov好店8网erridepublic void removeallkey(int key) {  node cur = this.head;  while (cur != null) {    if (cur.data == key) {      // 头节点      if (cur == this.head) {        this.head = this.head.next;        this.head.prev = null;      } el {        cur.prev.next = cur.next;        // cur.next != null --->不是尾节点        if (cur.next != null) {          cur.next.prev = cur.prev;        } el {          this.last = cur.prev;        }      }    }    cur = cur.next;  }}

7. 得到单链表的长度

/*** 7.得到单链表的长度* @return*/@overridepublic int getlength() {  int count = 0;  node cur = this.head;  while (cur != null) {    count++;    cur = cur.next;  }  return count;}

8. 打印链表

/*** 8.打印链表*/@overridepublic void display() {  if (this.head == null) {    return ;  }  node cur = this.head;  while (cur != null) {    system.out.print(cur.data + " ");    cur = cur.next;  }  system.out.println();}

9. 清空顺序表以防内存泄漏

/*** 9.清空顺序表以防内存泄漏*/@overridepublic void clear() {  while(this.head != null) {    node cur = this.head.next;    this.head.next = nu黄河之水天上来全诗ll;    this.head.prev = null;    this.head = cur;  }}

接口、实现方法、测试

1. 接口

package com.github.doubly;// 不带头节点单链表的实现public interface idoublelinked {  // 1.头插法  void addfirst(int data);  // 2.尾插法  void addlast(int data);  // 3.任意位置插入，第一个数据节点为0号下标  boolean addindex(int index, int data);  // 4.查找是否包含关键字 key 在单链表中  boolean contains(int key);  // 5.删除第一次出现关键字为 key 的节点  int remove(int key);  // 6.删除所有值为 key 的节点  void removeallkey(int key);  // 7.得到单链表的长度  int getlength();  // 8.打印链表  void display();  // 9.清空顺序表以防内存泄漏  void clear();}

2. 实现方法

package com.github.doubly;public class doublelinked implements idoublelinked {  class node {    private int data;    private node next;    private node prev;    public node(int data) {      this.data = data;      this.prev = null;      this.next = null;    }  }  private node head; // 头节点  private node last; // 尾节点  public doublelinked() {    this.head = null;    this.last = null;  }  /**  * 1.头插法  * @param data  */  @override  public void addfirst(int data) {    node node = new node(data);    if (this.head == null) {      this.head = node;      this.last = node;    } el {      node.next = this.head;      this.head.prev = node;      this.head = node;    }  }  /**  * 2.尾插法  * @param data  */  @override  public void addlast(int data) {    node node = new node(data);    if (this.head == null) {      this.head = node;      this.last = node;    } el {      this.last.next = node;      node.prev = this.last;      this.last = node;    }  }  // 查找  private node archindex(int index) {    checkindex(index);    int count = 0;    node cur = this.head;    while (count != index) {      cur = cur.next;      count++;    }    return cur;  }  // 合法性检查  private void checkindex(int index) {    if (index < 0 || index > getlength()) {      throw new indexoutofboundxception("下标不合法！");    }  }  /**  * 3.任意位置插入，第一个数据节点为0号下标  * @param index 插入位置  * @param data 插入的值  * @return true/fal  */  @override  public boolean addindex(int index, int data) {    if (index ==0) {      addfirst(data);      return true;    }    if (index == getlength()) {      addlast(data);      return true;    }    // cur 指向index位置的节点    node cur = archindex(index);    node node = new node(data);    node.next = cur;    cur.prev.next = node;    node.prev = cur.prev;    cur.prev = node;    return true;  }  /**  * 4.查找是否包含关键字 key 在单链表中  * @param key 要查找的关键字  * @return true/fal  */  @override  public boolean contains(int key) {    node cur = this.head;    while (cur != null) {      if (cur.data == key) {        return true;      }      cur = cur.next;    }    return fal;  }  /**  * 5.删除第一次出现关键字为 key 的节点  * @param key  * @return  */  @override  public int remove(int key) {    node cur = this.head;    int olddata = 0;    while (cur != null) {      if (cur.data == key) {        olddata = cur.data;        // 头节点        if (cur == this.head) {          this.head = this.head.next;          this.head.prev = null;        } el {          // cur.next != null --->不是尾节点          if (cur.next != null) {            cur.next.prev = cur.prev;          } el {            this.last = cur.prev;          }        }        return olddata;      }      cur = cur.next;    }    return -1;  }  /**  * 6.删除所有值为 key 的节点  * @param key  */  @override  public void removeallkey(int key) {    node cur = this.head;    while (cur != null) {      if (cur.data == key) {        // 头节点        if (cur == this.head) {          this.head = this.head.next;          this.head.prev = null;        } el {          cur.prev.next = cur.next;          // cur.next != null --->不是尾节点          if (cur.next != null) {            cur.next.prev = cur.prev;          } el {            this.last = cur.prev;          }        }      }      cur = cur.nexedgvsahqt;    }  }  /**  * 7.得到单链表的长度  * @return  */  @override  public int getlength() {    int count = 0;    node cur = this.head;    while (cur != null) {      count++;      cur = cur.next;    }    return count;  }  /**  * 8.打印链表  */  @override  public void display() {    if (this.head == null) {      return ;    }    node cur = this补偿流.head;    while (cur != null) {      system.out.print(cur.data + " ");      cur = cur.next;    }    system.out.println();  }  /**  * 9.清空顺序表以防内存泄漏  */  @override  public void clear() {    while(this.head != null) {      node cur = this.head.next;      this.head.nex材料采购合同t = null;      this.head.prev = null;      this.head = cur;    }  }}

3. 测试

package com.github.doubly;public class testdemo {  public static void main(string[] args) {    doublelinked doublelinked = new doublelinked();    doublelinked.addfirst(10);    doublelinked.addfirst(20);    doublelinked.addfirst(30);    doublelinked.addfirst(40);    doublelinked.addfirst(50);    doublelinked.display();    doublelinked.addindex(0,100);    doublelinked.addindex(1,200);    doublelinked.addindex(0,300);    doublelinked.addlast(40);    doublelinked.addlast(50);    doublelinked.display();    doublelinked.remove(300);    doublelinked.display();    doublelinked.removeallkey(50);    doublelinked.display();  }}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持www.887551.com。