用Java实现双向链表
用Java实现双向链表，并完成以下操作
1.insertBefore(p,d):将值d插入到列表中p之前的位置，并返回插入数据的位置
2.insertAfter(p, d):将值d插入到列表中p之后的位置，并返回插入数据的位置
3.insertFirst(d):将值d插入到列表的第一个位置，并返回插入数据的位置
4.insertLast(d):将值d插入到列表的最后一个位置，并返回插入数据的位置
5.remove (p):从列表中删除位置p，并返回存储在其中的数据
/**
* 节点类
*/
class Node{
public String value;
public Node next;
public Node pre;
//构造器
public Node(String value) {
this.value = value;
}
@Override
public String toString() {
return "DoublePersonNode [value=" + value + "]";
}
}
/**
* 链表的关键部分，封装了增删改查的方法类
*/
class DoubleLink{
//先创建一个头节点
Node head = new Node("");
//将值d插入到列表中p之前的位置
public int insertBefore(Node d, String p) {
int index = 0;
//辅助变量
Node temp = head;
//遍历到链表的尾部
while(true) {
if(p.equals(temp.next.value)) {
//temp已经找到了要插入的位置
break;
}
//后移
temp = temp.next;
index ++;
}
//开始加入节点
d.next = temp.next;
temp.next.pre = d;
temp.next = d;
d.pre = temp;
return index;
}
//将值d插入到列表中p之后的位置
public int insertAfter(Node d, String p) {
int index = 0;
//需要一个临时变量
Node temp = head;
//遍历到链表的尾部
while(true) {
if(p.equals(temp.value)) {
//temp已经找到了要插入的位置
break;
}
//后移
temp = temp.next;
index ++;
}
//开始加入节点
temp.next = d;
d.pre = temp;
return index;
}
//增加在链表第一个位置
public int insertFirst(Node d) {
if(head.next != null) {
head.next.pre = d;
d.next = head.next;
head.next = d;
d.pre = head;
}else {
head.next = d;
d.pre = head;
}
return 0;
}
//增加在链表最后一个位置
public int insertLast(Node d) {
int index = 0;
//需要一个临时变量
Node temp = head;
//遍历到链表的尾部
while(true) {
if(temp.next == null) {
//temp已经指到链表尾部
break;
}
//后移
temp = temp.next;
index ++;
}
//开始加入节点
temp.next = d;
d.pre = temp;
return index;
}
//删除位置p的节点
public String remove(int p) {
int index = 0;
//需要一个临时变量
Node temp = head.next;
//需要一个变量来判断是否找到删除的位置
boolean flag = false;
for(int i=0; i<p; i++) {
temp = temp.next;
}
temp.pre.next = temp.next;
if(temp.next != null) {
temp.next.pre = temp.pre;
}
return temp.value;
}
//查询显示节点
public void show() {
if(head.next == null) {
//为空提示
System.out.println("链表为空");
}else {
//需要一个临时变量
Node temp = head.next;
while(true) {
if(temp == null) {
break;
}
//输出
System.out.print(temp);
//后移
temp = temp.next;
}
}
}
//测试运行
public static void main(String args[]) {
DoubleLink doubleLink = new DoubleLink();
int aIndex = doubleLink.insertFirst(new Node("a"));
System.out.println("在第"+ aIndex +"个位置插入一个节点");
int bIndex = doubleLink.insertAfter(new Node("b"), "a");
System.out.println("在第"+ bIndex +"个位置插入一个节点");
int cIndex = doubleLink.insertBefore(new Node("c"), "b");
System.out.println("在第"+ cIndex +"个位置插入一个节点");
int dIndex = doubleLink.insertLast(new Node("d"));
System.out.println("在第"+ dIndex +"个位置插入一个节点");
String removeValue = doubleLink.remove(3);
System.out.println("删除的节点值为：" + removeValue);
doubleLink.show();
}
}
public class MyLinkedList {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
for (int i = 5; i > 0; i--) {
myLinkedList.insertFirst(i);
}
myLinkedList.display();
for (int i = 8; i < 11; i++) {
myLinkedList.insertLast(i);
}
myLinkedList.display();
myLinkedList.insertAfter(4, 7);
myLinkedList.display();
myLinkedList.insertBefore(5, 6);
myLinkedList.display();
System.out.println(myLinkedList.remove(5));
myLinkedList.display();
}
// 打印双向链表
public void display() {
ListNode cur = this.head;
if (cur == null) {
System.out.println("双向链表为空");
return;
}
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
static class ListNode {
public int val;
public ListNode next;
public ListNode prev;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;// 头节点
public ListNode tail;// 尾节点
// 求链表长度
public int size() {
ListNode cur = this.head;
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
// 头插法
public int insertFirst(int val) {
ListNode node = new ListNode(val);
if (this.head == null) {
this.head = node;
this.tail = node;
} else {
node.next = this.head;
this.head.prev = node;
this.head = node;
}
return 1;
}
// 尾插法
public int insertLast(int val) {
ListNode node = new ListNode(val);
if (this.head == null) {
this.head = node;
this.tail = node;
} else {
this.tail.next = node;
node.prev = this.tail;
this.tail = node;
}
return size();
}
public int insertBefore(int index, int val) {
return addIndex(index, val);
}
public int insertAfter(int index, int val) {
return addIndex(index + 1, val);
}
// 在index位置插入数据
public int addIndex(int index, int val) {
// 1.判断index合法性
if (index < 0 || index > size()) {
throw new RuntimeException("index位置不合法");
}
// 2.头插尾插
if (index == 0) {
return insertFirst(val);
}
if (index == size()) {
return insertLast(val);
}
// 3.找到index下标开始插入
ListNode cur = getIndex(index);
ListNode node = new ListNode(val);
node.next = cur;
node.prev = cur.prev;
cur.prev.next = node;
cur.prev = node;
return index;
}
private ListNode getIndex(int index) {
ListNode cur = this.head;
while (index > 0) {
cur = cur.next;
index--;
}
return cur;
}
public int remove(int index) {
final ListNode listNode = getIndex(index);
listNode.next.prev = listNode.prev;
listNode.prev.next = listNode.next;
return listNode.val;
}
}
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632
- 看下这篇博客，也许你就懂了，链接：Java用链表实现队列