目录
1.基本框架图
双向链表由数值域、两个地址域组成，head.prev =?null , last.next =?null
?
?2.头插法
?建立一个新节点 node，新链表的prev域和next域为null，将其插在链表的前面，最后就变成链表的第一个节点
3.尾插法
建立一个新节点 node，新链表的prev域和next域为null。原本节点last.next = node,node.prv = last,
最后last = node,这样新的节点就成了尾节点了
?4.任意位置插入
任意位置包括了头插、尾插、中间位置插。链表的节点数是从下标0开始数的，
我们在插入前，先找到要插入的位置，则被插入的位置就往后了一步。不是说真的往后移动了一步，只是下标增加了1
?
5.源码
?创建两个Java文件，
一个是链表的方法：
class ListNode {
public int val;
public ListNode prev;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
//双向链表
public class MyLinkedList {
public ListNode head;
public ListNode last;
//打印链表，和单链表一样
public void display() {
ListNode cur = head;
while(cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
//得到链表的长度
public int size() {
ListNode cur = head;
int count = 0;
while(cur != null) {
cur = cur.next;
count++;
}
return count;
}
//查找是否包含关键字key，是否在链表当中
public boolean contains(int key) {
ListNode cur = head;
while(cur != null) {
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
//头插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
if(this.head ==null) {
this.head = node;
this.last = node;
}else {
node.next = this.head;//后面的给前面
this.head.prev = node;//前面的给后面
this.head = node;//再放到前面去
}
}
//尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
if(this.head == null) {
this.head = node;
this.last = node;
}else {
this.last.next = node;//后面的给前面
node.prev = this.last;//前面的给后面
this.last = node;//再放到后面去
}
}
//找到要插入的位置
public ListNode searchIndex (int index) {
ListNode cur = this.head;
while (index != 0) {
cur = cur.next;
index--;
}
return cur;
}
//任意位置插入，第一个数据节点为0下标
public void addIndex(int index,int data) {
ListNode node = new ListNode(data);
if (index < 0 || index >size()) {
System.out.println("index位置不合法");
return;
}
//头插
if (index == 0) {
addFirst(data);
return;
}
//尾插
if (index == size()) {
addLast(data);
return;
}
//中间部位插
ListNode cur = searchIndex (index);
node.next = cur.prev.next;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
//删除第一次出现关键字key的位置
public void remove(int key) {
ListNode cur = head;
while(cur != null) {
if(cur.val == key) {
if(cur == head) {
head = head.next;
if(head != null) {
head.prev = null;
}else {
last = null;
}
}else {
cur.prev.next = cur.prev;
if(cur.next != null) {
//中间位置
cur.next.prev = cur.prev;
}else {
last = last.prev;
}
}
return;
}
cur = cur.next;
}
}
//删除重复节点
public void removeAllKey(int key) {
ListNode cur = head;
while(cur != null) {
if(cur.val == key) {
if(cur == head) {
head = head.next;
if(head != null) {
head.prev = null;
}else {
last = null;
}
}else {
cur.prev.next = cur.prev;
if(cur.next != null) {
//中间位置
cur.next.prev = cur.prev;
}else {
last = last.prev;
}
}
}
//删除一个继续往下走
cur = cur.next;
}
}
//清空链表
public void clear() {
ListNode cur = head;
while(cur != null) {
ListNode curNext = cur.next;
cur.next = null;
cur.prev = null;
cur = curNext;
}
//头和尾最后清空
last = null;
head = null;
}
}
?一个是主函数：
下面的主函数就简单实现几个方法（?尾插法、指定位置添加，打印，清空）
public class TestDemo {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addLast(4);
myLinkedList.addLast(3);
myLinkedList.display();
//myLinkedList.removeAllKey(3);
myLinkedList.addIndex(2,10);
myLinkedList.display();
myLinkedList.clear();
myLinkedList.display();
}
}?