代码拉取完成,页面将自动刷新
public class DoublyLinkedList<E> {
//---------------- nested Node class ----------------
/**
* Node of a doubly linked list, which stores a reference to its
* element and to both the previous and next node in the list.
*/
public static class Node<E> { // Sotiris: Changed this one to public
// this is a nested class
/** The element stored at this node */
private E element; // reference to the element stored at this node
/** A reference to the preceding node in the list */
private Node<E> prev; // reference to the previous node in the list
/** A reference to the subsequent node in the list */
private Node<E> next; // reference to the subsequent node in the list
/**
* Creates a node with the given element and next node.
*
* @param e the element to be stored
* @param p reference to a node that should precede the new node
* @param n reference to a node that should follow the new node
*/
public Node(E e, Node<E> p, Node<E> n) {
element = e;
prev = p;
next = n;
}
// public accessor methods
/**
* Returns the element stored at the node.
* @return the element stored at the node
*/
public E getElement() { return element; }
/**
* Returns the node that precedes this one (or null if no such node).
* @return the preceding node
*/
public Node<E> getPrev() { return prev; }
/**
* Returns the node that follows this one (or null if no such node).
* @return the following node
*/
public Node<E> getNext() { return next; }
// Update methods
/**
* Sets the node's previous reference to point to Node n.
* @param p the node that should precede this one
*/
public void setPrev(Node<E> p) { prev = p; }
/**
* Sets the node's next reference to point to Node n.
* @param n the node that should follow this one
*/
public void setNext(Node<E> n) { next = n; }
} //----------- end of nested Node class -----------
// instance variables of the DoublyLinkedList
/** Sentinel node at the beginning of the list */
private Node<E> header; // header sentinel
/** Sentinel node at the end of the list */
private Node<E> trailer; // trailer sentinel
/** Number of elements in the list (not including sentinels) */
private int size = 0; // number of elements in the list
private int capacity = 0;
/** Constructs a new empty list. */
public DoublyLinkedList() {
}
// public accessor methods
/**
* Returns the number of elements in the linked list.
* @return number of elements in the linked list
*/
public int size() { return size; }
/**
* Tests whether the linked list is empty.
* @return true if the linked list is empty, false otherwise
*/
public boolean isEmpty() { return size == 0; }
/**
* Returns the header sentinel node of the linked list.
* @return header node of the linked list
*/
public Node<E> getHeader() { // Sotiris: Added getHeader() you should consider whether you need set methods also
return header;
}
/**
* Returns the trailer sentinel node of the linked list.
* @return trailer node of the linked list
*/
public Node<E> getTrailer() { // Sotiris: Added getTrailer()
return trailer;
}
/**
* Returns (but does not remove) the first element of the list.
* @return element at the front of the list (or null if empty)
*/
public E first() {
if (isEmpty()) return null;
return header.getNext().getElement(); // first element is beyond header
}
/**
* Returns (but does not remove) the last element of the list.
* @return element at the end of the list (or null if empty)
*/
public E last() {
if (isEmpty()) return null;
return trailer.getPrev().getElement(); // last element is before trailer
}
// public update methods
/**
* Adds an element to the front of the list.
* @param e the new element to add
*/
public void addFirst(E e) {
header = new Node<>(e, null, header);
if (size == 0)
trailer = header;
size++ ;
}
/**
* Adds an element to the end of the list.
* @param e the new element to add
*/
public void addLast(E e) {
Node<E> newest = new Node<>(e, trailer, null);
if (isEmpty())
header = newest;
else
trailer.setNext(newest);
trailer = newest;
size++;
}
public void addIn(E e, Node<E> front, Node<E> back) {
addBetween(e, front, back);
}
/**
* Removes and returns the first element of the list.
* @return the removed element (or null if empty)
*/
public E removeFirst() {
if (isEmpty()) return null; // nothing to remove
return remove(header); // first element is beyond header
}
/**
* Removes and returns the last element of the list.
* @return the removed element (or null if empty)
*/
public E removeLast() {
if (isEmpty()) return null; // nothing to remove
return remove(trailer);
}
public E removeAt(Node<E> node) {
return remove(node);
}
public void newHead(E e, Node<E> before) {
Node<E> newest = new Node<>(e, null, before);
header = newest;
before.setPrev(header);
size++;
}
// private update methods
/**
* Adds an element to the linked list in between the given nodes.
* The given predecessor and successor should be neighboring each
* other prior to the call.
*
* @param predecessor node just before the location where the new element is inserted
* @param successor node just after the location where the new element is inserted
*/
private void addBetween(E e, Node<E> predecessor, Node<E> successor) {
// create and link a new node
Node<E> newest = new Node<>(e, predecessor, successor);
predecessor.setNext(newest);
successor.setPrev(newest);
size++;
}
/**
* Removes the given node from the list and returns its element.
* @param node the node to be removed (must not be a sentinel)
*/
private E remove(Node<E> node) {
Node<E> predecessor = node.getPrev();
Node<E> successor = node.getNext();
if(predecessor != null)
predecessor.setNext(successor);
else
header = successor;
if(successor != null)
successor.setPrev(predecessor);
else
trailer = predecessor;
size--;
return node.getElement();
}
/**
* Produces a string representation of the contents of the list.
* This exists for debugging purposes only.
*/
public String toString() {
StringBuilder sb = new StringBuilder("(");
Node<E> walk = header.getNext();
while (walk != trailer) {
sb.append(walk.getElement());
walk = walk.getNext();
if (walk != trailer)
sb.append(", ");
}
sb.append(")");
return sb.toString();
}
} //----------- end of DoublyLinkedList class -----------
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。