Java雙向鏈表的操作
前言
我們之前學的單鏈表，默認隻能從鏈表的頭部遍歷到鏈表的尾部，在實際中應用太少見，太局限；而雙向鏈表，對於該鏈表中的任意節點，既可以通過該節點向前遍歷，也可以通過該節點向後遍歷，雙向鏈表在實際工程中應用非常廣泛，是使用鏈表這個結構的首選。
一、認識雙向鏈表
單向鏈表不僅保存瞭當前的結點值，還保存瞭下一個結點的地址
雙向鏈表不僅保存瞭當前節點的值，還保存瞭上一個結點的地址和下一個結點的地址
定義一個雙向鏈表的結點類：
結點中既要保存當前節點的值，還要保存此節點的前驅節點的地址和此節點的後繼節點的地址
class DoubleNode{
public DoubleNode next;
DoubleNode prev;
int val;
DoubleNode tail;
public DoubleNode() {}
public DoubleNode(int val) {
this.val = val;
}
public DoubleNode(DoubleNode prev, int val, DoubleNode tail) {
this.prev = prev;
this.val = val;
this.tail = tail;
}
}
定義一個雙向鏈表類：
既可以從前向後，也可以從後向前，所以在這個類中，即保存一下頭結點，也保存一下尾結點的值
public class DoubleLinkedList {
private int size;
private DoubleNode head;
private DoubleNode tail;
}
二、雙向鏈表的增刪改查
1.插入
頭插
在當前鏈表的頭部插入一個節點，讓當前鏈表的頭結點head前驅指向要插入的節點node，然後讓node的後繼指向head，然後讓head = node，讓node成為鏈表的頭結點
代碼如下：
/**
* 頭插
*/
public void addFirst(int val){
DoubleNode node = new DoubleNode(val);
if (head == null){
head = tail = node;
}else{
node.next = head;
head.prev = node;
head = node;
}
size++;
}
尾插
和頭插一樣，隻不過在鏈表的尾部插入
代碼如下：
public void addLast(int val){
DoubleNode node = new DoubleNode(val);
if (head == null){
head = tail =node;
}else{
tail.next = node;
node.prev = tail;
tail = node;
}
size++;
}
在index位置插入
在索引為index的位置插入值為val的節點：
插入還是要找前驅節點，但雙向鏈表找前驅節點比單向鏈表找前驅節點要靈活很多，單向鏈表隻能從頭走到尾，假如此時有100個節點，要在索引為98的位置插入節點，那麼雙向鏈表就可以從尾結點開始找，會方便很多
如何判斷從前向後找，還是從後向前找？
- 1.index < size / 2 – >從前向後找，插入位置在前半部分
- 2.index > size / 2 – >從後向前找，插入位置在後半部分
代碼如下：
/**
* 在index位置插入
* @param index
* @param val
*/
public void add(int index,int val){
DoubleNode cur = new DoubleNode(val);
if (index < 0 || index > size){
System.err.println("add index illegal");
return;
}else{
if (index == 0){addFirst(val);}
else if (index == size){addLast(val);}
else{
DoubleNode prev = node(index-1);
DoubleNode next = prev.next;
cur.next = next;
next.prev = cur;
prev.next = cur;
cur.prev = prev;
}
}
size++;
}
/**
* 根據索引值找到對應的結點
* @param index
* @return
*/
private DoubleNode node(int index){
DoubleNode x = null;
if (index < size/2){
x = head;
for (int i = 0; i < index; i++) {
x = x.next;
}
}else{
x = tail;
for (int i = size - 1; i > index ; i--) {
x = x.prev;
}
}
return x;
}
2.修改
代碼如下：
/**
* 修改雙向鏈表index位置的結點值為newVal
*/
public int set(int index,int newVal){
DoubleNode dummyHead = new DoubleNode();
dummyHead.next = head;
DoubleNode prev = dummyHead;
DoubleNode cur = prev.next;
if (index < 0 || index > size - 1){
System.err.println("set index illegal");
}else{
for (int i = 0; i < index; i++) {
prev = prev.next;
cur = cur.next;
}
}
int oldVal = cur.val;
cur.val = newVal;
return oldVal;
}
3.查詢
代碼如下：
/**
* 查詢index位置的結點值
*/
public int get(int index){
DoubleNode dummyHead = new DoubleNode();
dummyHead.next = head;
DoubleNode prev = dummyHead;
DoubleNode cur = prev.next;
if (index < 0 || index > size - 1){
System.err.println("get index illegal");
}else{
for (int i = 0; i < index; i++) {
prev = prev.next;
cur = cur.next;
}
}
return cur.val;
}
4.刪除
刪除index位置的節點
代碼如下：
//刪除鏈表index位置的結點
public void removeIndex(int index){
if (index < 0 || index > size - 1){
System.err.println("remove index illegal");
return;
}
DoubleNode cur = node(index);
unlink(cur);
}
/**
* 刪除當前雙向鏈表的node結點
* 分治法
* @param node
*/
private void unlink (DoubleNode node){
DoubleNode prev = node.prev;
DoubleNode successor = node.next;
//1.先處理node的前半部分
if (prev == null){
head = successor;
}else{
//前驅不為空的情況
prev.next = successor;
node.prev = null;
}
if (successor == null){
tail = prev;
}else{
successor.prev = prev;
node.next = null;
}
size--;
}
頭刪
調用刪除任意位置的節點即可
代碼如下：
//頭刪
public void removeFirst(){
removeIndex(0);
}
尾刪
調用刪除任意位置的節點即可
代碼如下：
//尾刪
public void removeLast(){
removeIndex(size - 1);
}
刪除第一個值為val的節點
代碼如下：
//刪除第一個值為val的結點
public void removeValOnce(int val){
if (head == null){
return;
}
for (DoubleNode x = head;x != null;x = x.next){
if (x.val == val){
unlink(x);
break;
}
}
}
/**
* 刪除當前雙向鏈表的node結點
* 分治法
* @param node
*/
private void unlink (DoubleNode node){
DoubleNode prev = node.prev;
DoubleNode successor = node.next;
//1.先處理node的前半部分
if (prev == null){
head = successor;
}else{
//前驅不為空的情況
prev.next = successor;
node.prev = null;
}
if (successor == null){
tail = prev;
}else{
successor.prev = prev;
node.next = null;
}
size--;
}
刪除所有值為val的值
代碼如下：
//刪除鏈表中所有值為val的結點
public void removeAllVal(int val){
for (DoubleNode x = head;x != null;){
if (x.val == val){
//暫存一下x的下一個結點
DoubleNode next = x.next;
unlink(x);
x = next;
}else{
//val不是待刪除的元素
x = x.next;
}
}
}
/**
* 刪除當前雙向鏈表的node結點
* 分治法
* @param node
*/
private void unlink (DoubleNode node){
DoubleNode prev = node.prev;
DoubleNode successor = node.next;
//1.先處理node的前半部分
if (prev == null){
head = successor;
}else{
//前驅不為空的情況
prev.next = successor;
node.prev = null;
}
if (successor == null){
tail = prev;
}else{
successor.prev = prev;
node.next = null;
}
size--;
}
總結
本篇博客帶大傢瞭解瞭一下什麼是雙向鏈表，和單鏈表有什麼區別，已經雙向鏈表的一些基本的增刪改查的操作，
到此這篇關於Java雙向鏈表的操作的文章就介紹到這瞭,更多相關Java雙向鏈表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！