版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/lovoo/article/details/51771321
一、概述：
1、什么时双向链表：
链表中的每个节点即指向前面一个节点，也指向后面一个节点，就像丢手绢游戏一样，每个人都手拉手
2、从头部插入
要对链表进行判断，如果为空则设置尾节点为新添加的节点，如果不为空，还要设置头节点的一个前节点为新节点
3、从尾部进行插入
如果链表为空，则直接设置头节点为新添加的节点，否则设置尾节点的后一个节点为新添加的节点。同时设置新添加的节点的前一个节点为尾节点
4、从头部删除
判断节点是否有下个节点，如果没有则设置节点为null，并且删除下个节点指向前节点的指针
5、删除尾部节点
如果头节点没有其它节点，把尾节点设置为Null。否则设置尾节点前一个节点的next为Null。设置尾节点为前一个节点
6、删除方法
此时不需要记录last的Node
删除时使用current.previous.next= current.next;
package com.struct.linklist;
/**
* @描述 双向链表
* @项目名称 Java_DataStruct
* @包名 com.struct.linklist
* @类名 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;
}
/**
* 插入数据
* @param value
*/
public void insertFirst(long value){
Node newNode = new Node(value);
if (first == null) {
last = newNode;
}else {
first.previous = newNode;
//把first节点往下移动
newNode.next = first;
}
//把插入的节点作为新的节点
first = newNode;
}
/**
* 插入数据
* @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;
}
//把最后个节点设置为最新的节点
last = newNode;
}
public boolean isEmpty(){
return first == null;
}
/**
* 删除头节点时要去除两个指针,一个指向下个的next ,一个是next的previous指向前面的
*
* @param value
* @return
*/
public Node deleteFirst(){
if (first == null) {
throw new RuntimeException("链表数据不存在");
}
Node temp = first;
if (first.next == null) {
last = null;
}else {
first.next.previous = null;
}
first = temp.next;
return temp;
}
/**
* 删除头节点时要去除两个指针,一个指向下个的next ,一个是next的previous指向前面的
*
* @param value
* @return
*/
public Node deleteLast(){
if (first == null) {
throw new RuntimeException("链表数据不存在");
}
Node temp = last;
if (first.next == null) {
last = null;
//把第一个删除
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("没找到节点");
return null;
}
current = current.next;
}
if (current == first) {
//return deleteFirst();
//指向下个就表示删除第一个
first = first.next;
}else {
current.previous.next = current.next;
}
return current;
}
/**
* 显示所有的数据
*/
public void display(){
if (first == null) {
//throw new RuntimeException("链表数据不存在");
return;
}
Node current = first;
while(current != null){
current.display();
current = current.next;
}
System.out.println("---------------");
}
/**
* 查找节点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("没找到");
return null;
}
return current;
}
/**
* 查找节点2
*
* @param key
* @return
*/
public Node findByKey(long key) {
Node current = first;
while (current.data != key) {
if (current.next == null) {
System.out.println("没找到");
return null;
}
current = current.next;
}
return current;
}
/**
* 根据索引查找对应的值
* @param position
* @return
*/
public Node findByPosition(int position){
Node current = first;
//为什么是position - 1，因为要使用遍历，让current指向下一个， 所以position - 1的下个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();
}
}