目錄
結構框圖
鏈表原始碼
函式主體
結構框圖
下面的是頭插法，傀儡節點一直是頭節點，是不會變動的，所以頭插法只能從傀儡節點下一個插入
其他方法和不帶頭的雙鏈表是差不多的
鏈表原始碼
class ListNode {
public int val;
public ListNode prev;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
//帶頭傀儡節點雙鏈表
public class HeadLinkedList {
public ListNode head = new ListNode(-1);//傀儡節點
public ListNode last;
//頭插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
//1.鏈表中只有傀儡節點的情況下
if(this.head.next == null) {
this.head.next = node;
node.prev = this.head;
this.last = node;
}else {
//鏈表中有兩個節點起，從后面往前連
node.next = this.head.next;
this.head.next.prev = node;
this.head.next = node;
node.prev = this.head;
}
}
//尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
if (this.head.next == null) {
this.head.next = node;
node.prev = this.head;
this.last = node;
}else {
this.last.next = node;
node.prev = this.last;
this.last = node;
}
}
//列印鏈表
public void display() {
ListNode cur = this.head;
while (cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
//找到要插入的位置
public ListNode searchIndex (int index) {
ListNode cur = this.head;
while (index != 0) {
cur = cur.next;
index--;
}
return cur;
}
//任意位置插入(先找到要插入的位置)，第一個資料節點為0下標
public void addIndex(int index,int data) {
ListNode node = new ListNode(data);
//不合法情況
if (index < 0 || index >size()) {
System.out.println("index位置不合法");
return;
}
//頭插
if (index == 0) {
addFirst(data);
return;
}
//尾插
if (index == size()) {
addLast(data);
return;
}
//中間部位插
ListNode cur = searchIndex(index);
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
//鏈表的長度
public int size() {
ListNode cur = this.head;
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
//查找是否包含關鍵字key，是否在鏈表當中
public boolean contains(int key) {
ListNode cur = this.head;
while (cur != null) {
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
//洗掉第一次出現關鍵字key的位置
public void remove(int key) {
ListNode cur = this.head.next;
while (cur != null) {
if (cur.val == key) {
//從第二個開始
if (this.head.next.val == key) {
this.head.next = cur.next;
cur.next.prev = this.head;
} else {
//中間位置
cur.prev.next = cur.next;
if (cur.next != null) {
cur.next.prev = cur.prev;
} else {
//刪了尾巴就往前走
this.last = this.last.prev;
}
}
return;
}
cur = cur.next;
}
}
//洗掉重復節點//考慮的位置和無頭鏈表有區別（要注意）
public void removeAllKey(int key) {
//因為第一個是傀儡節點，所以從第二個開始
ListNode cur = this.head.next;
while (cur != null) {
if (cur.val == key) {
//從第二個開始
if (this.head.next.val == key) {
this.head.next = cur.next;
cur.next.prev = this.head;
}else {
//中間位置
cur.prev.next = cur.next;
if (cur.next != null) {
cur.next.prev = cur.prev;
}else {
this.last = this.last.prev;
}
}
// return;//就是在洗掉一次的前提下繼續往后走，直到走完鏈表
}
cur = cur.next;
}
}
//清空鏈表
public void clear() {
ListNode cur = this.head;
while (cur != null) {
ListNode curNext = cur.next;
cur.next = null;
cur.prev = null;
cur = curNext;
}
//傀儡節點最后再清空
head = null;
this.last = null;
}
}
函式主體
里面是鏈表的一些方法實作展示
public class TestDemo {
public static void main(String[] args) {
HeadLinkedList headLinkedList = new HeadLinkedList();
System.out.print("頭插：");
headLinkedList.addFirst(2);
headLinkedList.addFirst(5);
headLinkedList.display();
System.out.print("尾插：");
headLinkedList.addLast(2);
headLinkedList.addLast(5);
headLinkedList.display();
int ret = headLinkedList.size();
System.out.println("鏈表長度："+ret);
System.out.print("任意位置插入：");
headLinkedList.addIndex(2,10);
headLinkedList.display();
headLinkedList.remove(2);
System.out.print("洗掉第一次出現關鍵字2后：");
headLinkedList.display();
int ret2 = headLinkedList.size();
System.out.println("鏈表長度："+ret2);
headLinkedList.removeAllKey(5);
System.out.print("洗掉關鍵字為5后：");
headLinkedList.display();
headLinkedList.clear();
System.out.print("清空鏈表后：");
headLinkedList.display();
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/384260.html
標籤：其他