无头双向不循环链表的模拟
总共由四部分组成，一个拥有总体方法名+参数 的接口、一个异常类、一个方法类、一个测试类
先看我们写入的接口
public interface ILinkList {
// 2、无头双向链表实现
//头插法
void addFirst(int val);
//尾插法
void addLast(int val);
//任意位置插入,第一个数据节点为0号下标
void addIndex(int index,int val);
//查找是否包含关键字key是否在单链表当中
boolean contains(int val);
//删除第一次出现关键字为key的节点
void remove(int val);
//删除所有值为key的节点
void removeAllKey(int val);
//得到单链表的长度
int size();
void display();
void clear();
}
再看我们写的异常类
public class indexNotLegalException extends RuntimeException {
public indexNotLegalException(){
}
public indexNotLegalException(String msg){
super(msg);
}
}模拟链表类我们一一来罗列
这次由于是双向链表，所以我们在ListNode内部类中多了一个元素，增加了前驱结点
成员变量中也加入了prev
先写size，display和contains方法，因为前驱结点的增加不影响这三个方法的书写
头插与尾差由于多了一个前驱结点，所以要分析为空的情况，创建新的节点，使得新节点的前驱后继都为null
指定位置的插入需要考虑的有点多
1先捕捉异常，给的指定位置是否合法
2.如果大小为0，则进行头插，如果大小为size，则进行尾差
3.如果在中间，就用方法找到index位置的链表，进行插入
下图为index位置链表查找以及判断index是否合法
移除链表第一个指定元素
看起来繁琐，其实不繁琐
先考虑链表是否为空，如果为空不进行操作，创建cur来遍历链表
如果找到了，判断是不是头结点的
1.如果是头结点判断有没有下一个数据，两个处理起来不一样，如果存在，head=head.next，前驱再置空，如果不存在，head已经是null，直接last置空即可
2.如果不是头结点就直接前一个节点的后继结点为当前的下一个，如果是尾节点直接last向前一步，如果不是，改变下一个的前驱结点为当前节点的前一个
然后直接返回，如果没找到继续遍历，直到遍历完
移除所有链表的指定元素
只需要将返回删除即可，一直遍历，直到结束
模拟方法的类总代码：
public class MyLinkList implements ILinkList{
public static class ListNode{
public int val;
public ListNode prev;
public ListNode next;
public ListNode(int val){
this.val=val;
}
}
ListNode head;
ListNode last;
@Override
public int size() {
ListNode cur=head;
int count=0;
while(cur!=null){
count++;
cur=cur.next;
}
return count;
}
@Override
public void display() {
ListNode cur=head;
while(cur!=null){
System.out.print(cur.val+" ");
cur=cur.next;
}
System.out.println();
}
@Override
public void clear() {
ListNode cur=head;
ListNode next;
while(cur!=null){
next=cur.next;
cur.prev=cur.next=null;
cur=next;
}
head=null;
last=null;
}
@Override
public void addFirst(int val) {//头插
ListNode node = new ListNode(val);
if (head == null) {
head = last = node;
head.prev = head.next = null;
} else {
node.next = head;
head.prev = node;
head = node;
}
}
@Override
public void addLast(int val) {
ListNode node=new ListNode(val);
if (head == null) {
head = last = node;
head.prev = head.next = null;
} else {
last.next=node;
node.prev=last;
last=node;
}
}
@Override
public void addIndex(int index, int val) {
try{
cheakIndexOfAddIndex(index);
}catch(indexNotLegalException e) {
e.printStackTrace();
}
if(index==0){
addFirst(val);//头插
return ;
}
if(index==size()){
addLast(val);//尾差
return;
}
//
ListNode cur=findeIndexOfNode(index);
ListNode node=new ListNode(val);
node.next=cur;
node.prev=cur.prev;
node.prev.next=node;
node.next.prev=node;
}
private ListNode findeIndexOfNode(int index){//找到index位置
ListNode cur=head;
while(index>0){
cur=cur.next;
index--;
}
return cur;
}
private void cheakIndexOfAddIndex(int index) throws indexNotLegalException{//判断index是否合法
if(index<0||index>size()){
throw new indexNotLegalException("index大小不合法");
}
}
@Override
public boolean contains(int val) {
ListNode cur=head;
while(cur!=null){
if(cur.val==val){
return true;
}
cur=cur.next;
}
return false;
}
@Override
public void remove(int val) {
ListNode cur=head;
while(cur!=null){
if (cur.val==val) {
if(cur==head){
head=head.next;
if(head!=null){
head.prev=null;
}else{
last=null;
}
}else{
cur.prev.next=cur.next;
if(cur.next==null){
last=last.prev;
}else{
cur.next.prev=cur.prev;
}
}
return;
}
cur=cur.next;
}
}
@Override
public void removeAllKey(int val) {
ListNode cur=head;
while(cur!=null){
if (cur.val==val) {
if(cur==head){
head=head.next;
if(head!=null){
head.prev=null;
}else{
last=null;
}
}else{
cur.prev.next=cur.next;
if(cur.next==null){
if(last!=head)
last=last.prev;
}else{
cur.next.prev=cur.prev;
}
}
}
cur=cur.next;
}
}
}