Java實現(xiàn)雙鏈表的示例代碼
更新時間：2022年09月26日 09:10:37 作者：熬夜磕代碼丶
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。本文將用Java語言實現(xiàn)雙鏈表，需要的可以參考一下
一、雙向鏈表是什么
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個結(jié)點開始，都可以很方便地訪問它的前驅(qū)結(jié)點和后繼結(jié)點。一般我們都構(gòu)造雙向循環(huán)鏈表。
LinkedList底層就是一個雙向鏈表，我們來實現(xiàn)一個雙向鏈表。
這里多一個尾指針，方便我們對尾插操作從O(n)降到O(1).每個結(jié)點多了前驅(qū)結(jié)點，方便我們對鏈表進行操作。
二、具體方法實現(xiàn)
定義結(jié)點
class ListNode {
int value;
ListNode next;
ListNode prev;
public ListNode(int value) {
this.value = value;
}
}
下標訪問異常
public class IndexWrongException extends RuntimeException{
public IndexWrongException() {
}
public IndexWrongException(String message) {
super(message);
}
}
獲取鏈表長度
class ListNode {
int value;
ListNode next;
ListNode prev;
public ListNode(int value) {
this.value = value;
}
}
打印鏈表
class ListNode {
int value;
ListNode next;
ListNode prev;
public ListNode(int value) {
this.value = value;
}
}
清空鏈表
public void clear(){
if(this.head == null) {
return;
}
ListNode cur = this.head;
while(cur != null) {
ListNode curNext = cur.next;
cur.prev = null;
cur.next = null;
cur = curNext;
}
head = null;
tail = null;
}
頭插法
public void addFirst(int data){
ListNode node = new ListNode(data);
if(head == null) {
this.head = node;
this.tail = node;
return;
}
node.next = this.head;
this.head.prev = node;
this.head = node;
}
尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
if(head == null) {
this.head = node;
this.tail = node;
return;
}
tail.next = node;
node.prev = tail;
tail = node;
}
指定位置插入
public void addIndex(int index,int data) throws IndexWrongException{
if(index < 0 || index > size()) {
throw new IndexWrongException("輸入下標不合法");
}
ListNode node = new ListNode(data);
if(index == 0) {
addFirst(data);
return;
}
if(index == size()) {
addLast(data);
return;
}
ListNode cur = this.head;
while(index != 0) {
cur = cur.next;
index--;
}
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}查找元素
public boolean contains(int key){
if(head == null) {
return false;
}
ListNode cur = this.head;
while(cur != null) {
if(cur.value == key) {
return true;
}
cur = cur.next;
}
return false;
}
刪除第一次出現(xiàn)的關(guān)鍵字
public void remove(int key){
ListNode cur = head;
while(cur != head) {
if(cur.value == key) {
if(cur == head) {
head = head.next;
if(head.next != null) {
head.prev = null;
}else {
tail = null;
}
}else {
cur.prev.next = cur.next;
if(cur.next != null) {
cur.next.prev = cur.prev;
}else {
tail = cur.prev;
tail.next = null;
}
}
return;
}
cur = cur.next;
}
}刪除所有值為key的節(jié)點
public void removeAllKey(int key){
ListNode cur = head;
while(cur != head) {
if(cur.value == key) {
if(cur == head) {
head = head.next;
if(head.next != null) {
head.prev = null;
}else {
tail = null;
}
}else {
cur.prev.next = cur.next;
if(cur.next != null) {
cur.next.prev = cur.prev;
}else {
tail = cur.prev;
tail.next = null;
}
}
}
cur = cur.next;
}
}三、完整代碼
public class LinkedList {
static class ListNode {
int value;
ListNode next;
ListNode prev;
public ListNode(int value) {
this.value = value;
}
}
ListNode head;
ListNode tail;
//頭插法
public void addFirst(int data){
ListNode node = new ListNode(data);
if(head == null) {
this.head = node;
this.tail = node;
return;
}
node.next = this.head;
this.head.prev = node;
this.head = node;
}
//尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
if(head == null) {
this.head = node;
this.tail = node;
return;
}
tail.next = node;
node.prev = tail;
tail = node;
}
//任意位置插入,第一個數(shù)據(jù)節(jié)點為0號下標
public void addIndex(int index,int data) throws IndexWrongException{
if(index < 0 || index > size()) {
throw new IndexWrongException("輸入下標不合法");
}
ListNode node = new ListNode(data);
if(index == 0) {
addFirst(data);
return;
}
if(index == size()) {
addLast(data);
return;
}
ListNode cur = this.head;
while(index != 0) {
cur = cur.next;
index--;
}
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
//查找是否包含關(guān)鍵字key是否在單鏈表當中
public boolean contains(int key){
if(head == null) {
return false;
}
ListNode cur = this.head;
while(cur != null) {
if(cur.value == key) {
return true;
}
cur = cur.next;
}
return false;
}
//刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點
public void remove(int key){
ListNode cur = head;
while(cur != head) {
if(cur.value == key) {
if(cur == head) {
head = head.next;
if(head.next != null) {
head.prev = null;
}else {
tail = null;
}
}else {
cur.prev.next = cur.next;
if(cur.next != null) {
cur.next.prev = cur.prev;
}else {
tail = cur.prev;
tail.next = null;
}
}
return;
}
cur = cur.next;
}
}
//刪除所有值為key的節(jié)點
public void removeAllKey(int key){
ListNode cur = head;
while(cur != head) {
if(cur.value == key) {
if(cur == head) {
head = head.next;
if(head.next != null) {
head.prev = null;
}else {
tail = null;
}
}else {
cur.prev.next = cur.next;
if(cur.next != null) {
cur.next.prev = cur.prev;
}else {
tail = cur.prev;
tail.next = null;
}
}
}
cur = cur.next;
}
}
//得到單鏈表的長度
public int size(){
ListNode cur = head;
int count = 0;
while(cur != null) {
cur = cur.next;
count++;
}
return count;
}
public void display(){
ListNode cur = head;
while (cur != null) {
System.out.print(cur.value+" ");
cur = cur.next;
}
System.out.println();
}
public void clear(){
if(this.head == null) {
return;
}
ListNode cur = this.head;
while(cur != null) {
ListNode curNext = cur.next;
cur.prev = null;
cur.next = null;
cur = curNext;
}
head = null;
tail = null;
}
}
到此這篇關(guān)于Java實現(xiàn)雙鏈表的示例代碼的文章就介紹到這了,更多相關(guān)Java雙鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
延遲初始化也叫做惰性初始化,指不提前初始化Bean,而是只有在真正使用時才創(chuàng)建及初始化Bean,本文主要介紹了Spring延遲Bean初始化的實現(xiàn)示例,感興趣的可以了解一下2024-06-06
這篇文章主要介紹了SpringBoot 集成 Druid過程解析,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-09-09
這篇文章主要介紹了Java數(shù)字簽名算法DSA,結(jié)合實例形式分析了Java數(shù)字簽名算法DSA具體定義與使用技巧,需要的朋友可以參考下2018-05-05
JDK的一個Bug監(jiān)聽文件變更的初步實現(xiàn)思路
這篇文章主要介紹了JDK的一個Bug監(jiān)聽文件變更要小心了,本篇文章就帶大家簡單實現(xiàn)一個對應(yīng)的功能，并分析一下對應(yīng)的Bug和優(yōu)缺點，需要的朋友可以參考下2022-05-05
DiscoveryClient是專門負責(zé)服務(wù)注冊和發(fā)現(xiàn)的，我們可以通過它獲取到注冊到注冊中心的所有服務(wù)，這篇文章主要介紹了Nacos?Discovery服務(wù)治理,需要的朋友可以參考下2022-11-11
Java 時間格式轉(zhuǎn)換之impleDateFormat與Data API解析與使用
想必大家對 SimpleDateFormat 并不陌生。SimpleDateFormat 是 Java 中一個非常常用的類，他是以區(qū)域敏感的方式格式化和解析日期的具體類。 它允許格式化 (date -> text)、語法分析 (text -> date)和標準化2021-11-11
JPA中@JoinColumn的name和referencedColumnName屬性的區(qū)別及說明
這篇文章主要介紹了JPA中@JoinColumn的name和referencedColumnName屬性的區(qū)別及說明,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-05-05
這篇文章主要介紹了Java多線程中斷機制三種方法及示例，向大家分享了這三種方法的介紹幾代碼示例，具有一定參考價值，需要的朋友可以了解下。2017-11-11
SpringBoot Mybatis批量插入Oracle數(shù)據(jù)庫數(shù)據(jù)
這篇文章主要介紹了SpringBoot Mybatis批量插入Oracle數(shù)據(jù)庫數(shù)據(jù)，文章圍繞主題展開詳細的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-08-08
這篇文章主要為大家介紹了本真的REST架構(gòu)風(fēng)格的深入理解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-03-03