【Java】LinkedList模拟实现

整体框架

IMyLinkedList接口

这个接口用来存放所有方法，之后用MyLinkedList来实现这个接口，重写里面的方法

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

IndexNotLegalException异常类

IndexNotLegalExceprion异常类用来判断index是否合法

public class IndexNotLegalException extends RuntimeException{public IndexNotLegalException() {}public IndexNotLegalException(String msg) {super(msg);}
}

MyLinkedList类

成员变量(节点信息)

static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode (int val){this.val = val;}}public ListNode head;public ListNode last;

addFirst(头插)

public void addFirst(int data) {ListNode newNode = new ListNode(data);if(head == null){head = last = newNode;}else{newNode.next = head;head.prev = newNode;head = newNode;}}

addLast(尾插)

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

在指定位置插入数据

public void addIndex(int index, int data) {//判断index的合法性try{checkIndex(index);}catch(IndexNotLegalException e){e.printStackTrace();}if(index == 0){addFirst(data);return;}if(index == size()){addLast(data);return;}ListNode newNode = new ListNode(data);ListNode cur = head;while(index != 0){cur = cur.next;index--;}newNode.next = cur;newNode.prev = cur.prev;cur.prev.next = newNode;cur.prev = newNode;}private void checkIndex(int index){if(index<0 || index>size()){throw new IndexNotLegalException("Index不合法...");}}

判断是否存在

public boolean contains(int key) {ListNode cur = head;while(cur != null){if(cur.val == key){return true;}cur = cur.next;}return false;}

移除第一个相等的节点

public void remove(int key) {ListNode cur = head;if(head.val == key && head == last){head = last = null;return;}//如果删除的在head节点if(head.val == key){head = head.next;head.prev = null;return;}while(cur != null){if(cur.val == key){cur.prev.next = cur.next;if(cur.next == null){last = cur.prev;break;}cur.next.prev = cur.prev;}cur = cur.next;}}

移除所有相等的节点

public void removeAllKey(int key) {ListNode cur = head;if(head.val == key && head == last){head = last = null;return;}//如果删除的在head节点if(head.val == key){head = head.next;head.prev = null;}while(cur != null){if(cur.val == key){cur.prev.next = cur.next;if(cur.next == null){last = cur.prev;break;}cur.next.prev = cur.prev;}cur = cur.next;}}

链表的长度

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

打印链表

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

释放回收链表

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