DoublyLinkedList

65 阅读 0 评论 43 点赞

我是靠谱客的博主彪壮柠檬，这篇文章主要介绍DoublyLinkedList，现在分享给大家，希望可以做个参考。

package lab.sodino.linklist; public class LinkedNode { private Object value; private LinkedNode preNode; private LinkedNode nextNode; public LinkedNode(Object obj) { this.value = obj; } public Object getValue() { return value; } public LinkedNode getPreNode() { return preNode; } public void setPreNode(LinkedNode node) { preNode = node; } public LinkedNode getNextNode() { return nextNode; } public void setNextNode(LinkedNode node) { nextNode = node; } }

package lab.sodino.linklist; public class DoublyLinkedList { private int size; private LinkedNode firstNode; private LinkedNode lastNode; public DoublyLinkedList() { size = 0; firstNode = null; } public int size() { return size; } public boolean add(Object obj) { return insert(obj, size); } public boolean insert(Object obj, int idx) { if (obj == null) { return false; } if (idx > size) { idx = size; } LinkedNode node = new LinkedNode(obj); if (idx == 0) { addFirstNode(node); } else if (idx == size) { addLastNode(node); } else { addMiddletNode(node, idx); } size++; return true; } private void initOriginalNode(LinkedNode node) { firstNode = node; firstNode.setPreNode(firstNode); firstNode.setNextNode(firstNode); lastNode = node; } private void addFirstNode(LinkedNode node) { if (firstNode == null) { initOriginalNode(node); } else { LinkedNode lastFirst = firstNode; firstNode = node; lastNode.setNextNode(firstNode); firstNode.setPreNode(lastNode); firstNode.setNextNode(lastFirst); lastFirst.setPreNode(firstNode); } } private void addMiddletNode(LinkedNode node, int idx) { LinkedNode lastIdxNode = getLinkedNode(idx); LinkedNode preIdxNode = lastIdxNode.getPreNode(); preIdxNode.setNextNode(node); node.setPreNode(preIdxNode); node.setNextNode(lastIdxNode); lastIdxNode.setPreNode(node); } private void addLastNode(LinkedNode node) { if (lastNode == null) { initOriginalNode(node); } else { LinkedNode lastLast = lastNode; lastNode = node; lastLast.setNextNode(lastNode); lastNode.setPreNode(lastLast); lastNode.setNextNode(firstNode); firstNode.setPreNode(lastNode); } } public boolean remove(int idx) { LinkedNode removeNode = getLinkedNode(idx); if (removeNode == null) { return false; } else { if (size > 1) { LinkedNode preRemoveNode = removeNode.getPreNode(); LinkedNode nextRemoveNode = removeNode.getNextNode(); preRemoveNode.setNextNode(nextRemoveNode); nextRemoveNode.setPreNode(preRemoveNode); } else { firstNode = lastNode = null; } size--; return true; } } public int getIndex(Object obj) { int idx = -1; int count = -1; LinkedNode currentNode = lastNode; do { count++; currentNode = currentNode.getNextNode(); if (obj == (currentNode.getValue())) { idx = count; break; } } while (count < size); return idx; } public boolean remove(LinkedNode node) { if (size == 0) { return false; } LinkedNode removeNode = null; int count = -1; LinkedNode currentNode = lastNode; do { count++; currentNode = currentNode.getNextNode(); if (currentNode == node) { removeNode = currentNode; break; } } while (count < size); if (removeNode == null) { return false; } else { if (size > 1) { LinkedNode preRemoveNode = removeNode.getPreNode(); LinkedNode nextRemoveNode = removeNode.getNextNode(); preRemoveNode.setNextNode(nextRemoveNode); nextRemoveNode.setPreNode(preRemoveNode); } else { firstNode = lastNode = null; } size--; return true; } } public boolean removeAll() { firstNode = lastNode = null; size = 0; return true; } private LinkedNode getLinkedNode(int idx) { if (idx < 0 || idx >= size) { return null; } int count = -1; LinkedNode currentNode = lastNode; do { count++; currentNode = currentNode.getNextNode(); } while (count != idx); return currentNode; } public Object getObject(int idx) { LinkedNode node = getLinkedNode(idx); if (node == null) { return null; } else { return node.getValue(); } } public LinkedNode getFirstNode() { return firstNode; } public LinkedNode getLastNode() { return lastNode; } }