无头双向链表的实现

1.头插法

public void addFirst(int data) { //头插 DLinkedNode newNode = new DLinkedNode(data);//加入的新节点 DLinkedNode next = head.next; newNode.next = next; next.prev = newNode; head.next = newNode; newNode.prev = head; }

2.尾插法

public void addLast(int data) {//尾插 DLinkedNode newNode = new DLinkedNode(data);//新插入的节点 DLinkedNode prev = head.prev; newNode.next = head; head.prev = newNode; newNode.prev = prev; prev.next = newNode; }

3.任意位置插入,第一个数据节点为0号下标

public void addIndex(int index,int data) {//任意位置插入 int size = size(); if(index < 0 || index > size){ return; } if(index == 0){ addFirst(data); return; } if(index == size) { addLast(data); return; } DLinkedNode next = getPos(index); DLinkedNode prev = next.prev; DLinkedNode newNode = new DLinkedNode(data); prev.next = newNode; newNode.prev = prev; next.prev = newNode; newNode.next = next; }

这里用到的计算链表长度的方法：

public int size(){ int size = 0; for(DLinkedNode cur = head.next; cur != head; cur = cur.next) { size++; } return size; }

和查找链表中某一位置的方法：

public DLinkedNode getPos(int index) { DLinkedNode cur = head.next; for(int i = 0; i < index; i++){ cur = cur.next; } return cur; }

4.查找是否包含关键字key是否在链表当中

public boolean contains(int key) {//查找是否包含关键字key的节点 for(DLinkedNode cur = head.next; cur != head; cur = cur.next) { if(cur.val == key){ return true; } } return false; }

5.删除第一次出现关键字为key的节点

public void remove(int key){ DLinkedNode toRemove = find(key); if(toRemove == null) { return; } DLinkedNode prev = toRemove.prev; DLinkedNode next = toRemove.next; prev.next = next; next.prev = prev; }

这里用到查找关键字key在链表中的位置的方法：

public DLinkedNode find(int key) { for(DLinkedNode cur = head.next; cur != head; cur = cur.next) { if(cur.val == key){ return cur; } } return null; }

6.删除所有值为key的节点

public void removeAll(int key){ while (true){ DLinkedNode toRmove = find(key); if(toRmove == null){ return; } DLinkedNode prev = toRmove.prev; DLinkedNode next = toRmove.next; prev.next = next; next.prev = prev; } }

7.打印链表

public void display(){ System.out.print("正向:["); for(DLinkedNode cur = head.next; cur != head; cur = cur.next){ System.out.print(cur.val); if(cur.next != head){ System.out.print(","); } } System.out.println("]"); System.out.println("反向:["); for(DLinkedNode cur = head.prev; cur != head; cur = cur.prev){ System.out.print(cur.val); if(cur.prev != head){ System.out.print(","); } } System.out.println("]"); }

8.清空链表

public void clear(){ head.next = head; head.prev = head; }