一、双向链表是什么
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
LinkedList底层就是一个双向链表，我们来实现一个双向链表。
这里多一个尾指针，方便我们对尾插操作从O(n)降到O(1).每个结点多了前驱结点，方便我们对链表进行操作。
二、具体方法实现
定义结点
class ListNode {
int value;
ListNode next;
ListNode prev;
public ListNode(int value) {
this.value = value;
}
}
下标访问异常
public class IndexWrongException extends RuntimeException{
public IndexWrongException() {
}
public IndexWrongException(String message) {
super(message);
}
}
获取链表长度
class ListNode {
int value;
ListNode next;
ListNode prev;
public ListNode(int value) {
this.value = value;
}
}
打印链表
class ListNode {
int value;
ListNode next;
ListNode prev;
public ListNode(int value) {
this.value = value;
}
}
清空链表
public void clear(){
if(this.head == null) {
return;
}
ListNode cur = this.head;
while(cur != null) {
ListNode curNext = cur.next;
cur.prev = null;
cur.next = null;
cur = curNext;
}
head = null;
tail = null;
}
头插法
public void addFirst(int data){
ListNode node = new ListNode(data);
if(head == null) {
this.head = node;
this.tail = node;
return;
}
node.next = this.head;
this.head.prev = node;
this.head = node;
}
尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
if(head == null) {
this.head = node;
this.tail = node;
return;
}
tail.next = node;
node.prev = tail;
tail = node;
}
指定位置插入
public void addIndex(int index,int data) throws IndexWrongException{
if(index < 0 || index > size()) {
throw new IndexWrongException("输入下标不合法");
}
ListNode node = new ListNode(data);
if(index == 0) {
addFirst(data);
return;
}
if(index == size()) {
addLast(data);
return;
}
ListNode cur = this.head;
while(index != 0) {
cur = cur.next;
index--;
}
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}查找元素
public boolean contains(int key){
if(head == null) {
return false;
}
ListNode cur = this.head;
while(cur != null) {
if(cur.value == key) {
return true;
}
cur = cur.next;
}
return false;
}
删除第一次出现的关键字
public void remove(int key){
ListNode cur = head;
while(cur != head) {
if(cur.value == key) {
if(cur == head) {
head = head.next;
if(head.next != null) {
head.prev = null;
}else {
tail = null;
}
}else {
cur.prev.next = cur.next;
if(cur.next != null) {
cur.next.prev = cur.prev;
}else {
tail = cur.prev;
tail.next = null;
}
}
return;
}
cur = cur.next;
}
}删除所有值为key的节点
public void removeAllKey(int key){
ListNode cur = head;
while(cur != head) {
if(cur.value == key) {
if(cur == head) {
head = head.next;
if(head.next != null) {
head.prev = null;
}else {
tail = null;
}
}else {
cur.prev.next = cur.next;
if(cur.next != null) {
cur.next.prev = cur.prev;
}else {
tail = cur.prev;
tail.next = null;
}
}
}
cur = cur.next;
}
}三、完整代码
public class LinkedList {
static class ListNode {
int value;
ListNode next;
ListNode prev;
public ListNode(int value) {
this.value = value;
}
}
ListNode head;
ListNode tail;
//头插法
public void addFirst(int data){
ListNode node = new ListNode(data);
if(head == null) {
this.head = node;
this.tail = node;
return;
}
node.next = this.head;
this.head.prev = node;
this.head = node;
}
//尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
if(head == null) {
this.head = node;
this.tail = node;
return;
}
tail.next = node;
node.prev = tail;
tail = node;
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data) throws IndexWrongException{
if(index < 0 || index > size()) {
throw new IndexWrongException("输入下标不合法");
}
ListNode node = new ListNode(data);
if(index == 0) {
addFirst(data);
return;
}
if(index == size()) {
addLast(data);
return;
}
ListNode cur = this.head;
while(index != 0) {
cur = cur.next;
index--;
}
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key){
if(head == null) {
return false;
}
ListNode cur = this.head;
while(cur != null) {
if(cur.value == key) {
return true;
}
cur = cur.next;
}
return false;
}
//删除第一次出现关键字为key的节点
public void remove(int key){
ListNode cur = head;
while(cur != head) {
if(cur.value == key) {
if(cur == head) {
head = head.next;
if(head.next != null) {
head.prev = null;
}else {
tail = null;
}
}else {
cur.prev.next = cur.next;
if(cur.next != null) {
cur.next.prev = cur.prev;
}else {
tail = cur.prev;
tail.next = null;
}
}
return;
}
cur = cur.next;
}
}
//删除所有值为key的节点
public void removeAllKey(int key){
ListNode cur = head;
while(cur != head) {
if(cur.value == key) {
if(cur == head) {
head = head.next;
if(head.next != null) {
head.prev = null;
}else {
tail = null;
}
}else {
cur.prev.next = cur.next;
if(cur.next != null) {
cur.next.prev = cur.prev;
}else {
tail = cur.prev;
tail.next = null;
}
}
}
cur = cur.next;
}
}
//得到单链表的长度
public int size(){
ListNode cur = head;
int count = 0;
while(cur != null) {
cur = cur.next;
count++;
}
return count;
}
public void display(){
ListNode cur = head;
while (cur != null) {
System.out.print(cur.value+" ");
cur = cur.next;
}
System.out.println();
}
public void clear(){
if(this.head == null) {
return;
}
ListNode cur = this.head;
while(cur != null) {
ListNode curNext = cur.next;
cur.prev = null;
cur.next = null;
cur = curNext;
}
head = null;
tail = null;
}
}
到此这篇关于Java实现双链表的示例代码的文章就介绍到这了,更多相关Java双链表内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
