專(zhuān)注Java教育14年
全國(guó)咨詢(xún)/投訴熱線：400-8080-105
更新時(shí)間：2019-08-21 13:59:11 來(lái)源：動(dòng)力節(jié)點(diǎn) 瀏覽2347次
一、概述：
1、什么時(shí)雙向鏈表：
鏈表中的每個(gè)節(jié)點(diǎn)即指向前面一個(gè)節(jié)點(diǎn)，也指向后面一個(gè)節(jié)點(diǎn)，就像丟手絹游戲一樣，每個(gè)人都手拉手
2、從頭部插入
要對(duì)鏈表進(jìn)行判斷，如果為空則設(shè)置尾節(jié)點(diǎn)為新添加的節(jié)點(diǎn)，如果不為空，還要設(shè)置頭節(jié)點(diǎn)的一個(gè)前節(jié)點(diǎn)為新節(jié)點(diǎn)
3、從尾部進(jìn)行插入
如果鏈表為空，則直接設(shè)置頭節(jié)點(diǎn)為新添加的節(jié)點(diǎn)，否則設(shè)置尾節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)為新添加的節(jié)點(diǎn)。同時(shí)設(shè)置新添加的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)為尾節(jié)點(diǎn)
4、從頭部刪除
判斷節(jié)點(diǎn)是否有下個(gè)節(jié)點(diǎn)，如果沒(méi)有則設(shè)置節(jié)點(diǎn)為null，并且刪除下個(gè)節(jié)點(diǎn)指向前節(jié)點(diǎn)的指針
5、刪除尾部節(jié)點(diǎn)
如果頭節(jié)點(diǎn)沒(méi)有其它節(jié)點(diǎn)，把尾節(jié)點(diǎn)設(shè)置為Null。否則設(shè)置尾節(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)的next為Null。設(shè)置尾節(jié)點(diǎn)為前一個(gè)節(jié)點(diǎn)
6、刪除方法
此時(shí)不需要記錄last的Node
刪除時(shí)使用current.previous.next= current.next;
二、實(shí)現(xiàn)
package com.struct.linklist;
/**
* @描述 雙向鏈表
* @項(xiàng)目名稱(chēng) Java_DataStruct
* @包名 com.struct.linklist
* @類(lèi)名 LinkList
* @author chenlin
* @date 2010年6月26日 上午8:00:28
* @version 1.0
*/
public class DoubleLinkList {
//頭
private Node first;
//尾
private Node last;
public DoubleLinkList(){
first = null;
last = null;
}
/**
* 插入數(shù)據(jù)
* @param value
*/
public void insertFirst(long value){
Node newNode = new Node(value);
if (first == null) {
last = newNode;
}else {
first.previous = newNode;
//把first節(jié)點(diǎn)往下移動(dòng)
newNode.next = first;
}
//把插入的節(jié)點(diǎn)作為新的節(jié)點(diǎn)
first = newNode;
}
/**
* 插入數(shù)據(jù)
* @param value
*/
public void insertLast(long value){
Node newNode = new Node(value);
if (first == null) {
first = newNode;
}else {
last.next = newNode;
//first.previous = newNode;
newNode.previous = last;
}
//把最后個(gè)節(jié)點(diǎn)設(shè)置為最新的節(jié)點(diǎn)
last = newNode;
}
public boolean isEmpty(){
return first == null;
}
/**
* 刪除頭節(jié)點(diǎn)時(shí)要去除兩個(gè)指針,一個(gè)指向下個(gè)的next ,一個(gè)是next的previous指向前面的
*
* @param value
* @return
*/
public Node deleteFirst(){
if (first == null) {
throw new RuntimeException("鏈表數(shù)據(jù)不存在");
}
Node temp = first;
if (first.next == null) {
last = null;
}else {
first.next.previous = null;
}
first = temp.next;
return temp;
}
/**
* 刪除頭節(jié)點(diǎn)時(shí)要去除兩個(gè)指針,一個(gè)指向下個(gè)的next ,一個(gè)是next的previous指向前面的
*
* @param value
* @return
*/
public Node deleteLast(){
if (first == null) {
throw new RuntimeException("鏈表數(shù)據(jù)不存在");
}
Node temp = last;
if (first.next == null) {
last = null;
//把第一個(gè)刪除
first = null;
}else {
last.previous.next = null;
}
last = temp.previous;
return temp;
}
/**
* 刪除
* @param key
* @return
*/
public Node deleteByKey(long key){
Node current = first;
while(current.data != key){
if (current.next == null) {
System.out.println("沒(méi)找到節(jié)點(diǎn)");
return null;
}
current = current.next;
}
if (current == first) {
//return deleteFirst();
//指向下個(gè)就表示刪除第一個(gè)
first = first.next;
}else {
current.previous.next = current.next;
}
return current;
}
/**
* 顯示所有的數(shù)據(jù)
*/
public void display(){
if (first == null) {
//throw new RuntimeException("鏈表數(shù)據(jù)不存在");
return;
}
Node current = first;
while(current != null){
current.display();
current = current.next;
}
System.out.println("---------------");
}
/**
* 查找節(jié)點(diǎn)1
* @param value
* @return
*/
public Node findByValue(long value){
Node current = first;
while(current != null){
if (current.data != value) {
current = current.next;
}else {
break;
}
}
if (current == null) {
System.out.println("沒(méi)找到");
return null;
}
return current;
}
/**
* 查找節(jié)點(diǎn)2
*
* @param key
* @return
*/
public Node findByKey(long key) {
Node current = first;
while (current.data != key) {
if (current.next == null) {
System.out.println("沒(méi)找到");
return null;
}
current = current.next;
}
return current;
}
/**
* 根據(jù)索引查找對(duì)應(yīng)的值
* @param position
* @return
*/
public Node findByPosition(int position){
Node current = first;
//為什么是position - 1，因?yàn)橐褂帽闅v，讓current指向下一個(gè)， 所以position - 1的下個(gè)node就是要找的值
for (int i = 0; i < position - 1 ; i++) {
current = current.next;
}
return current;
}
public static void main(String[] args) {
DoubleLinkList linkList = new DoubleLinkList();
linkList.insertFirst(21);
linkList.insertFirst(22);
linkList.insertFirst(23);
linkList.insertLast(24);
linkList.insertLast(25);
linkList.insertLast(26);
linkList.insertLast(27);
linkList.display();
System.out.println("---查找-------------------------------------");
linkList.findByKey(25).display();
System.out.println("--刪除first-------------------------------------");
//linkList.deleteFirst().display();
///linkList.deleteFirst().display();
//linkList.deleteFirst().display();
//linkList.deleteFirst().display();
System.out.println("-刪除指定值---------------------------------------");
linkList.deleteByKey(27).display();
linkList.deleteByKey(21).display();
System.out.println("----------------------------------------");
linkList.display();
}
}
相關(guān)閱讀
Java實(shí)驗(yàn)班
0基礎(chǔ) 0學(xué)費(fèi) 15天面授
Java就業(yè)班
有基礎(chǔ) 直達(dá)就業(yè)
Java夜校直播班
業(yè)余時(shí)間 高薪轉(zhuǎn)行
Java在職加薪班
工作1~3年，加薪神器
Java架構(gòu)師班
工作3~5年，晉升架構(gòu)
提交申請(qǐng)后，顧問(wèn)老師會(huì)電話與您溝通安排學(xué)習(xí)
京公網(wǎng)安備 11030102010736號(hào)