## 一、双向不循环链表的概念

public class MyLinkedList implements Ilist{
public ListNode last;//尾结点
static class ListNode {
int val;
ListNode next;
ListNode prev;
public ListNode(int val) {
this.val = val;
}
}
}

## 二、链表的接口

public interface Ilist {
//头插法
//尾插法
//任意位置插入,第一个数据节点为0号下标
//查找是否包含关键字key是否在单链表当中
boolean contains(int key);
//删除第一次出现关键字为key的节点
void remove(int key);
//删除所有值为key的节点
void removeAllKey(int key);
//得到单链表的长度
int size();
void clear();
void display();
}

## 三、链表的方法实现

### （1）display方法

public void display() {
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}

### （2）size方法

public int size() {
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}

### （3）contains方法

public int size() {
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}

public void addFirst(int data) {
ListNode cur = new ListNode(data);
this.last = cur;
} else {
}
}

public void addLast(int data) {
ListNode cur = new ListNode(data);
if(last == null) {
last = cur;
} else {
last.next = cur;
cur.prev = last;
last = cur;
}
}

public void addIndex(int index, int data) {
//检查下标是否合法
if(index < 0 || index > size()) {
throw new IndexException("下标不合法");
}
if(index == 0) {
return;
}
if (index == size()) {
return;
}
ListNode cur = new ListNode(data);
int count = 0;
while (count < index - 1) {
prev = prev.next;
count++;
}
ListNode prevNext = prev.next;
prev.next = cur;
cur.prev = prev;
cur.next = prevNext;
prevNext.prev = cur;
}
//自定义异常类
public class IndexException extends RuntimeException{
public IndexException(String e) {
super(e);
}
}

### （7）remove方法

public void remove(int key) {
return;
}
} else {
last = null;
return;
}
}
ListNode prev = findPrev(key);
if(prev == null) {
//没有要删的元素
return;
}
ListNode cur = prev.next;
if(cur.next != null) {
prev.next = cur.next;
cur.next.prev = cur.prev;
} else {
//最后一个元素
prev.next = cur.next;//null
last = prev;
}
}
//找到要删除节点的前一个节点
private ListNode findPrev(int key) {
ListNode curNext = cur.next;
while (curNext != null) {
if(curNext.val != key) {
cur = cur.next;
curNext = curNext.next;
} else {
return cur;
}
}
return null;
}

### （8）removeAllKey方法

public void removeAllKey(int key) {
return;
}
while (cur != null) {
if(cur.val == key) {
if(cur.next != null) {
prev.next = cur.next;
cur.next.prev = prev;
} else {
prev.next = cur.next;//null
last = prev;
}
cur = cur.next;
} else {
prev = prev.next;
cur = cur.next;
}
}
}
}
}

### （9）clear方法

public void clear() {
while (cur != null) {
ListNode curNext = cur.next;
cur.next = null;
cur.prev = null;
cur = curNext;
}
last = null;
}

## 四、最终代码

public class MyLinkedList implements Ilist{
public ListNode last;//尾结点
static class ListNode {
int val;
ListNode next;
ListNode prev;
public ListNode(int val) {
this.val = val;
}
}
@Override
ListNode cur = new ListNode(data);
this.last = cur;
} else {
}
}
@Override
ListNode cur = new ListNode(data);
if(last == null) {
last = cur;
} else {
last.next = cur;
cur.prev = last;
last = cur;
}
}
@Override
public void addIndex(int index, int data) {
//检查下标是否合法
if(index < 0 || index > size()) {
throw new IndexException("下标不合法");
}
if(index == 0) {
return;
}
if (index == size()) {
return;
}
ListNode cur = new ListNode(data);
int count = 0;
while (count < index - 1) {
prev = prev.next;
count++;
}
ListNode prevNext = prev.next;
prev.next = cur;
cur.prev = prev;
cur.next = prevNext;
prevNext.prev = cur;
}
@Override
public boolean contains(int key) {
while (cur != null) {
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
@Override
public void remove(int key) {
return;
}
} else {
last = null;
return;
}
}
ListNode prev = findPrev(key);
if(prev == null) {
//没有要删的元素
return;
}
ListNode cur = prev.next;
if(cur.next != null) {
prev.next = cur.next;
cur.next.prev = cur.prev;
} else {
//最后一个元素
prev.next = cur.next;//null
last = prev;
}
}
private ListNode findPrev(int key) {
ListNode curNext = cur.next;
while (curNext != null) {
if(curNext.val != key) {
cur = cur.next;
curNext = curNext.next;
} else {
return cur;
}
}
return null;
}
@Override
public void removeAllKey(int key) {
return;
}
while (cur != null) {
if(cur.val == key) {
if(cur.next != null) {
prev.next = cur.next;
cur.next.prev = prev;
} else {
prev.next = cur.next;//null
last = prev;
}
cur = cur.next;
} else {
prev = prev.next;
cur = cur.next;
}
}
}
}
}
@Override
public int size() {
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
@Override
public void clear() {
while (cur != null) {
ListNode curNext = cur.next;
cur.next = null;
cur.prev = null;
cur = curNext;
}
last = null;
}
@Override
public void display() {
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
}
//自定义异常类
public class IndexException extends RuntimeException{
public IndexException(String e) {
super(e);
}
}

## 都看到这了，点个赞再走吧，谢谢谢谢谢！！！

|
7天前

6 0
|
9天前

10 0
|
10天前

16 0
|
19天前
|

【数据结构】链表(单链表与双链表实现+原理+源码)
【数据结构】链表(单链表与双链表实现+原理+源码)
19 1
|
23天前
|

【数据结构】深入浅出理解链表中二级指针的应用
【数据结构】深入浅出理解链表中二级指针的应用
27 0
|
25天前
|

31 1
|
27天前
|

30 0
|
1月前
|

【双向链表】数据结构双向链表的实现
【双向链表】数据结构双向链表的实现
20 0
|
1月前
|

【单链表】数据结构单链表的实现
【单链表】数据结构单链表的实现
32 0
|
1月前
|

11 0