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;
} else {
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;
} else {
this.last.next = node;
node.prev = this.last;
this.last = node;
}
}
若鏈表為空，同頭插法；
若鏈表不為空，則把鏈表尾節點的 next 指向要插入節點，要插入節點的 prev 指向鏈表尾節點，最後更新尾節點為新插入節點，插入過程如下圖所示：
3. 查找是否包含關鍵字 key 在單鏈表中
// 查找
private Node searchIndex(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 IndexOutOfBoundsException("下標不合法！");
}
}
/**
* 3.任意位置插入，第一個數據節點為0號下標
* @param index 插入位置
* @param data 插入的值
* @return true/false
*/
@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 = searchIndex(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/false
*/
@Override
public boolean contains(int key) {
Node cur = this.head;
while (cur != null) {
if (cur.data == key) {
return true;
}
cur = cur.next;
}
return false;
}
5. 刪除第一次出現關鍵字為 key 的節點
/**
* 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;
} else {
// cur.next != null --->不是尾節點
if (cur.next != null) {
cur.next.prev = cur.prev;
} else {
this.last = cur.prev;
}
}
return oldData;
}
cur = cur.next;
}
return -1;
}
6. 刪除所有值為 key 的節點
/**
* 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;
} else {
cur.prev.next = cur.next;
// cur.next != null --->不是尾節點
if (cur.next != null) {
cur.next.prev = cur.prev;
} else {
this.last = cur.prev;
}
}
}
cur = cur.next;
}
}
7. 得到單鏈表的長度
/**
* 7.得到單鏈表的長度
* @return
*/
@Override
public int getLength() {
int count = 0;
Node cur = this.head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
8. 打印鏈表
/**
* 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. 清空順序表以防內存泄漏
/**
* 9.清空順序表以防內存泄漏
*/
@Override
public void clear() {
while(this.head != null) {
Node cur = this.head.next;
this.head.next = null;
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;
} else {
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;
} else {
this.last.next = node;
node.prev = this.last;
this.last = node;
}
}
// 查找
private Node searchIndex(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 IndexOutOfBoundsException("下標不合法！");
}
}
/**
* 3.任意位置插入，第一個數據節點為0號下標
* @param index 插入位置
* @param data 插入的值
* @return true/false
*/
@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 = searchIndex(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/false
*/
@Override
public boolean contains(int key) {
Node cur = this.head;
while (cur != null) {
if (cur.data == key) {
return true;
}
cur = cur.next;
}
return false;
}
/**
* 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;
} else {
// cur.next != null --->不是尾節點
if (cur.next != null) {
cur.next.prev = cur.prev;
} else {
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;
} else {
cur.prev.next = cur.next;
// cur.next != null --->不是尾節點
if (cur.next != null) {
cur.next.prev = cur.prev;
} else {
this.last = cur.prev;
}
}
}
cur = cur.next;
}
}
/**
* 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.next = 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();
}
}
以上就是本文的全部內容，希望對大傢的學習有所幫助，也希望大傢多多支持WalkonNet。