引言
在之前的博文中，我簡單的向大家分享了一些鏈表相關的知識及一些面試題，如果感興趣的老鐵可以去瞧瞧！今天給大家帶來雙向鏈表以及帶傀儡節點的雙向鏈表的實作，認真看，每一步都有具體的來由和理解，希望對大家有所幫助！
詳細步驟決議咋們邊看代碼邊學習！
雙向鏈表的實作
class ListNode{
public int val;//數值域
public ListNode prev;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public class DoubleLinkedList {
public ListNode head;//指向雙鏈表的頭節點
public ListNode last;//指向雙鏈表尾巴節點
//列印鏈表--和列印單鏈表的方式一樣
public void display(){
ListNode cur = this.head;
while (cur!=null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
//得到單鏈表的長度
public int size(){
int count = 0;//記錄節點個數
ListNode cur = this.head;
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) {//如果cur.val等于key回傳真
return true;
}//否則繼續往下走
cur = cur.next;
}
return false;
}
//頭插法
public void addFirst(int data){
ListNode node = new ListNode(data);//new了個插入節點
if(head == null) {//如果插入時鏈表為空則，頭和尾都指向新節點node
this.head = node;
this.last = node;
}else {
node.next = head;
head.prev = node;
this.head = node;
}
}
//尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
if(this.head == null) {
this.head = node;
this.last = node;
}else {
this.last.next = node;
node.prev = last;
this.last = node;
}
}
//任意位置插入,第一個資料節點為0號下標
public void addIndex(int index,int data){
ListNode node = new ListNode(data);
if(index<0 || index>size()){
System.out.println("index位置不合法");
}
if(index == 0) {
addFirst(data);
}
if(index==size()){
addLast(data);
}
ListNode cur = searchIndex(index);
node.next = cur.prev.next;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
public ListNode searchIndex(int index) {
ListNode cur = this.head;//創建個方法找到插入時cur的位置
while (index != 0) {
cur = cur.next;
index--;
}
return cur;
}
//洗掉第一次出現關鍵字為key的節點
//單鏈表中洗掉第一次出現的關鍵字需要找到關鍵字前驅
//雙鏈表只需要直接找到這個節點
public void remove(int key){
ListNode cur = this.head;
while (cur!=null) {
if(cur.val == key) {//這里分兩種情況
if(cur == head) {//1.cur等于頭結點
head = head.next;
head.prev = null;//手動置為空
}else {//2.cur不等于頭結點
cur.prev.next = cur.next;
if(cur.next!=null) {
//中間位置
cur.next.prev = cur.prev;
}else {//尾巴位置
last = last.prev;
}
}
return;
}else {
cur = cur.next;
}
}
}
//洗掉所有值為key的節點
public void removeAllKey(int key){
ListNode cur = this.head;
while (cur != null) {
if (cur.val == key) {
if (cur == head) {
head = head.next;
if (head != null) {
head.prev = null;
} else {
last = null;
}
} else {
cur.prev.next = cur.next;
if (cur.next != null) {
//中間位置
cur.next.prev = cur.prev;
} else {
last = last.prev;
}
}
//return;
}
cur = cur.next;
}
}
public void clear(){
while (head!=null) {
ListNode curNext = head.next;
head.next = null;
head.prev = null;
head = curNext;
}
last = null;
}
}
雙向鏈表增刪添改的實作
public class TestDemo {
public static void main(String[] args) {
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
doubleLinkedList.addLast(12);
doubleLinkedList.addLast(13);
doubleLinkedList.addLast(14);
doubleLinkedList.addLast(15);
doubleLinkedList.addLast(16);
doubleLinkedList.display();
System.out.println("=================");
doubleLinkedList.addIndex(3,99);
doubleLinkedList.display();
}
}
帶傀儡節點的雙向鏈表的實作
class ListNode{
public int val;
public ListNode next;
public ListNode prev;
public ListNode(int val) {
this.val = val;
}
}
public class DoubleLinkedList {//帶傀儡節點的雙鏈表
public ListNode dummyHead;//虛擬節點
public ListNode last;//尾節點
public DoubleLinkedList() {
this.dummyHead = new ListNode(-1);//傀儡節點
}
//列印單鏈表
public void display() {
ListNode cur = this.dummyHead.next;
//參考cur代替head，head等于傀儡節點下一個節點
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
//得到單鏈表的長度
public int size() {
int count = 0;//記錄節點個數
ListNode cur = this.dummyHead.next;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
//頭插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
//第一次插入一個節點都沒有的情況
if (this.dummyHead.next == null) {
node.prev = dummyHead;
this.dummyHead.next = node;
this.last = node;
return;
} else {
//新插入的節點和他前后節點連接
node.next = this.dummyHead.next;
node.prev = this.dummyHead;
this.dummyHead.next.prev = node;
this.dummyHead.next = node;
}
}
//尾插法
public void addLast(int data) {
ListNode node = new ListNode(-1);
//判斷頭節點是否為空
if (this.dummyHead.next == null && this.last.next == null) {
this.dummyHead.next = node;
node.prev = this.dummyHead;
this.last = node;
return;
} else {
this.last.next = node;
node.prev = last;
this.last = node;
}
}
//任意位置插入,第一個資料節點為0號下標
public void addIndex(int index, int data) {
ListNode node = new ListNode(data);
if(index<0 || index>size()){
System.out.println("index位置不合法");
return;
}else {
if(index == 0) {
addFirst(data);
}
if(index == size()) {
addLast(data);
}else {
//中間位置的時候
ListNode cur = searchIndex(index);
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
}
}
//創建個方法找到cur的位置
public ListNode searchIndex(int index) {
//先找到cur的位置
ListNode cur = this.dummyHead.next;
while (index!=0) {
cur = cur.next;
index--;
}
return cur;
}
//查找是否包含關鍵字key是否在單鏈表當中
public boolean contains(int key){
ListNode cur = this.dummyHead.next;
while (cur!=null) {
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
//洗掉第一次出現關鍵字為key的節點
//單鏈表中洗掉第一次出現的關鍵字需要找到關鍵字前驅
//雙鏈表只需要直接找到這個節點
public void remove(int key){
ListNode cur = this.dummyHead.next;
if(cur.val == key){//有兩種情況 cur=head或者cur不等于head
if(cur == this.dummyHead.next) {//cur==head時
this.dummyHead.next = this.dummyHead.next.next;
this.dummyHead.next.next.prev = null;
}else {//cur不等于head又有兩種情況
//1.cur在中間位置2.cur在最后的位置
cur.prev.next = cur.next;
//判斷是不是最后一個節點
//要洗掉的節點不是最后一個節點
if(cur.next!=null){
cur.next.prev = cur.prev;
}else {
this.last = cur.prev;
}
}
return;
}else {
cur = cur.next;
}
}
//洗掉所有值為key的節點
public void removeAllKey(int key){
ListNode cur = this.dummyHead.next;
while (cur!=null) {
if(cur.val == key){
if(cur == this.dummyHead.next) {
this.dummyHead.next = this.dummyHead.next.next;
this.dummyHead.next.prev = null;
}else {
cur.prev.next = cur.next;
//判斷如果是最后一個節點
if(cur.next == null) {
this.last = cur.prev;
}else {
cur.next.prev = cur.prev;
}
}
}
cur = cur.next;
}
}
public void clear(){
ListNode cur = this.dummyHead.next;
ListNode curNext = cur.next;
while (cur!=null) {
cur.prev = null;
cur.next = null;
cur = curNext;
}
this.dummyHead = null;
this.last = null;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/385589.html
標籤：java