双链表的结构
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
双链表的结构体（代码）
双链表，需要一个指向前驱的指针，后指向后继元素的指针，以及数据域。
package day01线性表;
public class DoubleListNode {
private Object data;//数据域
private DoubleListNode pre;//前驱
private DoubleListNode next;//后继
public DoubleListNode(Object data) {
this.data = data;
}
}
双链表的实现类
设置head和last两个哑元（其数据域并不存放数据），只是为了方便插入删除。
package day01线性表;
public class DoubleLinkedList implements MyList{
private DoubleListNode head = new DoubleListNode(null);//头节点哑元，数据域为空
private DoubleListNode last = new DoubleListNode(null);//尾点哑元，数据域为空
private int size;//记录节点个数
public DoubleLinkedList() {
//初始状态，头节点的后继是尾节点，尾节点的前驱是头节点
head.setNext(last);
last.setPre(head);
}
}
双链表中的插入和删除操作（核心）
插入：
插入的话，需要修改四个指针指向（修改顺序具有一定的规则！）
//尾插法，修改尾节点的前驱的后继
last.pre.next=p;
// 插入的节点的后继是尾节点
p.next = last;
// 插入节点的前驱是尾节点的前驱
p.pre = last.pre;
// 尾节点的前驱是插入的新节点
last.pre = p;
代码实现部分：
@Override
public void add(Object element) {
//双向链表的尾插法
DoubleListNode newNode = new DoubleListNode(element);
//尾插法，修改尾节点的前驱的后继
last.getPre().setNext(newNode);
// 插入的节点的后继是尾节点
newNode.setNext(last);
// 插入节点的前驱是尾节点的前驱
newNode.setPre(last.getPre());
// 尾节点的前驱是插入的新节点
last.setPre(newNode);
size++;
}
删除：
删除的话，只需要改变两个指针指向即可,并且前驱后继谁先修改不会影响结果。
//修改p的前驱的后继为p的后继
p.pre.next = p.next;
//修改p的后继的前驱为p的前驱
p.next.pre = p.pre;
代码实现部分：
//根据值删除
@Override
public void delete(Object element) {
//同样还是先记录头结点
DoubleListNode p = head.getNext();
// 因为双链表的删除，修改p的前驱的后继为p的后继，修改p的后继的前驱为p的前驱
// 然后释放掉p，在java垃圾回收机制中，将其设置为null 可以快速回收
while (p != last) {
if (p.getData().equals(element)) {
//修改p的前驱的后继为p的后继
p.getPre().setNext(p.getNext());
//修改p的后继的前驱为p的前驱
p.getNext().setPre(p.getPre());
//将p的前驱，后继都设置为Null,快速回收
p.setPre(null);
p.setNext(null);
size--;
return;
}
//没找到就一直往后面移动 p
p = p.getNext();
}
//如果就是整个链表中都没找到则打印输出
System.out.println("当前链表中中不存在值为"+element.toString()+"的元素，无法删除!");
}
// 根据索引删除
@Override
public void delete(int index) {
//index越界判断
if(index<0||index>=size){
System.out.println("要访问的索引已经越界!无法进行删除");
return;
}
int i = 0;//一开始头节点的索引为0
DoubleListNode p = head.getNext();
while (p!=last){
if(i==index){
//这里无论是先修改p的前驱。还是p的后继，都没有任何影响。因为是双向的
p.getNext().setPre(p.getPre());
p.getPre().setNext(p.getNext());
p.setNext(null);
p.setPre(null);
size--;
return;
}
//没找到就一直往后面移动 p
p = p.getNext();
i++;
}
}
双链表的其他操作及完整的代码
项目目录结构
DoubleListNode.java为结构体类，DoubleLinkedList.java为实现类，MyList.java为方法接口。
结构体
DoubleListNode.java：
package day01线性表;
public class DoubleListNode {
private Object data;//数据域
private DoubleListNode pre;//前驱
private DoubleListNode next;//后继
public DoubleListNode(Object data) {
this.data = data;
}
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public DoubleListNode getPre() {
return pre;
}
public void setPre(DoubleListNode pre) {
this.pre = pre;
}
public DoubleListNode getNext() {
return next;
}
public void setNext(DoubleListNode next) {
this.next = next;
}
}
方法接口
MyList.java：
package day01线性表;
public interface MyList {
/**
* 添加元素
* @param element
*/
void add(Object element);
/**
* 在指定位置插入元素
* @param target
* @param element
*/
void add(int target,Object element);
/**
* 根据元素的值来删除
* @param element
*/
void delete(Object element);
/**
* 根据索引来删除元素
* @param index
*/
void delete(int index);
/**
* 根据指定的target索引位置来更新元素
* @param traget
* @param element
*/
void update(int traget,Object element);
/**
* 返回某一元素第一次在线性表中出现的位置
* @param element
* @return
*/
int indexOf(Object element);
/**
* 返回在指定target位置的元素
* @param target
* @return
*/
Object elementAt(int target);
/**
* 取指定索引位置元素的前驱元素
* @param index
* @return
*/
Object elementPrior(int index);
/**
* 取指定索引位置元素的后继元素
* @param index
* @return
*/
Object elementNext(int index);
/**
* 是否包含某一元素
* @param element
* @return
*/
boolean contains(Object element);
}
实现类
DoubleLinkedList.java：
package day01线性表;
public class DoubleLinkedList implements MyList{
private DoubleListNode head = new DoubleListNode(null);//头节点哑元，数据域为空
private DoubleListNode last = new DoubleListNode(null);//尾点哑元，数据域为空
private int size;//记录节点个数
public DoubleLinkedList() {
//初始状态，头节点的后继是尾节点，尾节点的前驱是头节点
head.setNext(last);
last.setPre(head);
}
@Override
public void add(Object element) {
//双向链表的尾插法
DoubleListNode newNode = new DoubleListNode(element);
//尾插法，修改尾节点的前驱的后继
last.getPre().setNext(newNode);
// 插入的节点的后继是尾节点
newNode.setNext(last);
// 插入节点的前驱是尾节点的前驱
newNode.setPre(last.getPre());
// 尾节点的前驱是插入的新节点
last.setPre(newNode);
size++;
}
@Override
public void add(int target, Object element) {
//这里这个指定位置插入，对于单链表意义不大，所以就忽略不写了
}
@Override
public void delete(Object element) {
//同样还是先记录头结点
DoubleListNode p = head.getNext();
// 因为双链表的删除，修改p的前驱的后继为p的后继，修改p的后继的前驱为p的前驱
// 然后释放掉p，在java垃圾回收机制中，将其设置为null 可以快速回收
while (p != last) {
if (p.getData().equals(element)) {
//修改p的前驱的后继为p的后继
p.getPre().setNext(p.getNext());
//修改p的后继的前驱为p的前驱
p.getNext().setPre(p.getPre());
//将p的前驱，后继都设置为Null,快速回收
p.setPre(null);
p.setNext(null);
size--;
return;
}
//没找到就一直往后面移动 p
p = p.getNext();
}
//如果就是整个链表中都没找到则打印输出
System.out.println("当前链表中中不存在值为"+element.toString()+"的元素，无法删除!");
}
@Override
public void delete(int index) {
//index越界判断
if(index<0||index>=size){
System.out.println("要访问的索引已经越界!无法进行删除");
return;
}
int i = 0;//一开始头节点的索引为0
DoubleListNode p = head.getNext();
while (p!=last){
if(i==index){
//这里无论是先修改p的前驱。还是p的后继，都没有任何影响。因为是双向的
p.getNext().setPre(p.getPre());
p.getPre().setNext(p.getNext());
p.setNext(null);
p.setPre(null);
size--;
return;
}
//没找到就一直往后面移动 p
p = p.getNext();
i++;
}
}
@Override
public void update(int traget, Object element) {
//index越界判断
if(traget<0||traget>=size){
System.out.println("要访问的索引已经越界!无法进行修改");
return;
}
int i = 0;//一开始头节点的索引为0
DoubleListNode p = head.getNext();
while (p!=last){
if(i==traget){
p.setData(element);
return;
}
//没找到就一直往后面移动 p
p = p.getNext();
i++;
}
}
@Override
public int indexOf(Object element) {
int i = 0;
DoubleListNode p = head.getNext();
while(p!=last){
if(p.getData().equals(element)){
return i;
}
p = p.getNext();
i++;
}
return -1;//整个链表中并没有对应的元素，则返回-1
}
@Override
public Object elementAt(int target) {
if(target<0||target>=size){
System.out.println("索引越界,已经超过链表的元素个数");
return null;
}
int i = 0;
DoubleListNode p = head.getNext();
while (p!=last) {
if (i == target) {
return p.getData();
}
p = p.getNext();
i++;
}
return null;
}
@Override
public Object elementPrior(int index) {
//索引越界
if(index-1<0||index>size){
return null;
}
int i =0;
DoubleListNode p = head.getNext();
while (p!=last){
if (i==index-1){
return p.getData();
}
p = p.getNext();
i++;
}
return null;
}
@Override
public Object elementNext(int index) {
//索引越界
if(index<0||index+1>size){
return null;
}
int i =0;
DoubleListNode p = head.getNext();
while (p!=last){
if (i==index+1){
return p.getData();
}
p = p.getNext();
i++;
}
return null;
}
@Override
public boolean contains(Object element) {
DoubleListNode p = head.getNext();
while (p!=last){
if(p.getData().equals(element)){
return true;
}
p = p.getNext();
}
return false;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
DoubleListNode p = head.getNext();
while (p!=last){
stringBuilder.append(p.getData());
if(p.getNext()!=last){
stringBuilder.append(",");
}
p = p.getNext();
}
stringBuilder.append("]");
return stringBuilder.toString();
}
public static void main(String[] args) {
DoubleLinkedList dbLinkedList = new DoubleLinkedList();
dbLinkedList.add("a");
dbLinkedList.add("b");
dbLinkedList.add("c");
dbLinkedList.add("d");
dbLinkedList.add("e");
System.out.println(dbLinkedList);
dbLinkedList.delete("c");
System.out.println(dbLinkedList);
System.out.println(dbLinkedList.contains("c"));
System.out.println(dbLinkedList.contains("a"));
System.out.println(dbLinkedList.elementAt(1));
dbLinkedList.delete(3);
System.out.println(dbLinkedList);
System.out.println(dbLinkedList.elementPrior(1));
System.out.println(dbLinkedList.elementNext(1));
}
}
main函数测试输出：
到此结束啦，java数据结构持续更新中！！！
