Java實作無頭雙向鏈表
- 雙向鏈表節點的定義
- 1.鏈表的列印
- 2.頭插法
- 3.尾插法
- 4.任意位置插入
- 5.查找鏈表中是否包含關鍵字 key
- 6.洗掉第一次出現關鍵字為 key 的節點
- 7.洗掉所有出現關鍵字為 key 的節點
- 8.鏈表長度
- 9.鏈表清空
- 附全部代碼：
介紹：
雙向鏈表比單鏈表多了一個 prev(前驅) 域，指向前一個節點data：資料
next：后繼資訊
prev：前驅資訊
.
無頭雙向鏈表圖解：
雙向鏈表節點的定義
class Node{
public int data;//資料
public Node next;//后繼資訊
public Node prev;//前驅資訊
//提供構造方法
public Node(int data){
this.data = data;
}
}
1.鏈表的列印
直接上代碼：
public void print(){
Node cur = this.head;
while(cur != null){
System.out.print(cur.data+" ");
cur = cur.next;
}
System.out.println();
}
2.頭插法
思考：
- 首先判斷是不是第一次插入
- 若是第一次插入，讓 head 和 tail 都指向 待插入節點node
- 若不是第一次插入，修改對應的值實作頭插即可
- 圖解：
代碼實作：
public void addFirst(int data){
Node node = new Node(data);
//第一次插入
if(this.head == null){
this.head = node;
this.tail = node;
}
//不是第一次插入
else{
node.next = this.head;
this.head.prev = node;
this.head = node;
}
}
3.尾插法
思考：
思考程序與頭插法一樣，參考頭插法
- 程序圖解：
代碼實作：
public void addLast(int data){
Node node = new Node(data);
//第一次插入
if(this.head == null){
this.head = node;
this.tail = node;
}
//不是第一次插入
else{
this.tail.next = node;
node.prev = this.tail;
this.tail = node;
}
}
4.任意位置插入
思考：
- 判斷Index的合法性
- 首先判斷是否是第一次插入—頭插
- 若不是，再判斷是否插入到最后位置—尾插
- 中間位置插入，需要考慮四個位置，如下圖：
- 圖解：
代碼實作：
private void checkIndex(int index){
if(index < 0 || index > len()){
throw new RuntimeException("index不合法！！");
}
}
private Node searchIndex(int index){
Node cur = this.head;
while(index != 0) {
cur = cur.next;
index--;
}
return cur;
}
public void addIndex(int index,int data){
checkIndex(index);
if(index == 0){
addFirst(data);
return;
}
if(index == len()){
addLast(data);
return;
}
Node node = new Node(data);
Node cur = searchIndex(index);
node.next = cur;
node.prev = cur.prev;
cur.prev.next = node;
cur.prev = node;
}
5.查找鏈表中是否包含關鍵字 key
比較簡單，直接貼代碼：
public boolean containKey(int key){
Node cur = this.head;
while(cur != null){
if(cur.data == key){
return true;
}
cur = cur.next;
}
return false;
}
6.洗掉第一次出現關鍵字為 key 的節點
思考：
- 直接上圖解：
代碼實作：
public void deleteKey(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;
if(cur.next != null){
cur.next.prev = cur.prev;
}
//洗掉的是尾節點,只需要移動tail
else{
this.tail = cur.prev;
}
}
}
cur = cur.next;
}
}
7.洗掉所有出現關鍵字為 key 的節點
思考：
根據洗掉第一次出現關鍵字為 key 的節點，修改代碼即可，考慮特殊情況
代碼實作：
public void deleteAllKey(int key){
Node cur = this.head;
while(cur != null){
if(cur.data == key){
//頭節點
if(cur == this.head){
this.head = this.head.next;
if(this.head != null){
this.head.prev = null;
}
}
//中間節點
else{
cur.prev.next = cur.next;
if(cur.next != null){
cur.next.prev = cur.prev;
}
//洗掉的是尾節點,只需要移動tail
else{
this.tail = cur.prev;
}
}
}
cur = cur.next;
}
}
8.鏈表長度
比較簡單，直接貼代碼：
public int len(){
int count = 0;
Node cur = this.head;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
9.鏈表清空
首先會想到以下代碼：
public void clear(){
this.head = null;
}
測驗打斷點除錯：
System.out.println("==============="); DoubleLinkedList doubleLinkedList3 = new DoubleLinkedList(); doubleLinkedList3.addLast(1); doubleLinkedList3.addLast(2); doubleLinkedList3.addLast(3); doubleLinkedList3.addLast(4); doubleLinkedList3.print(); doubleLinkedList3.clear(); System.out.println("!!!!!!!!!!!!!!!!!!!!!");
然后打開 cmd：
- 輸入jps
- 重定義到一個文本檔案
- 找到 log.txt 所在目錄，打開 log.txt
- 雙擊打開后，ctrl + f，搜索Node
仍然有4個，說明插入的4個資料沒有被回收掉！
故：僅僅將 head 置為null，不能實作鏈表清空
解決方法：
大家可以按照上述除錯檢測，資料是否被回收~
public void clear(){
//一個一個節點進行釋放
while(this.head != null){
Node cur = this.head.next;
this.head.prev = null;
this.head.next = null;
this.head = cur;
}
this.tail = null;
}
附全部代碼：
class Node{
public int data;//資料
public Node next;//后繼資訊
public Node prev;//前驅資訊
//提供構造方法
public Node(int data){
this.data = data;
}
}
public class DoubleLinkedList {
public Node head; //表示雙向鏈表的頭
public Node tail; //表示當前雙向鏈表的尾
//1.列印鏈表
public void print(){
Node cur = this.head;
while(cur != null){
System.out.print(cur.data+" ");
cur = cur.next;
}
System.out.println();
}
//2.頭插法
public void addFirst(int data){
Node node = new Node(data);
//第一次插入
if(this.head == null){
this.head = node;
this.tail = node;
}
//不是第一次插入
else{
node.next = this.head;
this.head.prev = node;
this.head = node;
}
}
//3.尾插法
public void addLast(int data){
Node node = new Node(data);
//第一次插入
if(this.head == null){
this.head = node;
this.tail = node;
}
//不是第一次插入
else{
this.tail.next = node;
node.prev = this.tail;
this.tail = node;
}
}
private void checkIndex(int index){
if(index < 0 || index > len()){
throw new RuntimeException("index不合法！！");
}
}
private Node searchIndex(int index){
Node cur = this.head;
while(index != 0) {
cur = cur.next;
index--;
}
return cur;
}
//4.任意位置插入，第一個資料節點為0號下標
public void addIndex(int index,int data){
checkIndex(index);
if(index == 0){
addFirst(data);
return;
}
if(index == len()){
addLast(data);
return;
}
Node node = new Node(data);
Node cur = searchIndex(index);
node.next = cur;
node.prev = cur.prev;
cur.prev.next = node;
cur.prev = node;
}
//5.查找鏈表中是否包含關鍵字 key
public boolean containKey(int key){
Node cur = this.head;
while(cur != null){
if(cur.data == key){
return true;
}
cur = cur.next;
}
return false;
}
//6.洗掉第一次出現關鍵字為 key 的節點
public void deleteKey(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;
if(cur.next != null){
cur.next.prev = cur.prev;
}
//洗掉的是尾節點,只需要移動tail
else{
this.tail = cur.prev;
}
}
}
cur = cur.next;
}
}
//7.洗掉所有關鍵字為 key 的節點
public void deleteAllKey(int key){
Node cur = this.head;
while(cur != null){
if(cur.data == key){
//頭節點
if(cur == this.head){
this.head = this.head.next;
if(this.head != null){
this.head.prev = null;
}
}
//中間節點
else{
cur.prev.next = cur.next;
if(cur.next != null){
cur.next.prev = cur.prev;
}
//洗掉的是尾節點,只需要移動tail
else{
this.tail = cur.prev;
}
}
}
cur = cur.next;
}
}
//8.鏈表長度
public int len(){
int count = 0;
Node cur = this.head;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
//9.鏈表清空
public void clear(){
//一個一個節點進行釋放
while(this.head != null){
Node cur = this.head.next;
this.head.prev = null;
this.head.next = null;
this.head = cur;
}
this.tail = null;
}
}
快下來試著敲敲叭~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/297142.html
標籤：其他