溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹了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();
}
}
感謝你能夠認真閱讀完這篇文章，希望小編分享的“Java如何實現無頭雙向鏈表操作”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，更多相關知識等著你來學習!
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
