Java is the #1 programming language and development platform. Itreduces costs, shortens development timeframes, drives innovation,and improves application services. With millions of developersrunning more than 51 billion Java Virtual Machines worldwide, Javacontinues to be the development platform of choice for enterprisesand developers.
- Rec5 Java Is The 1 Programming Language And Development Platform It Reduces Costs Shortens Development Timeframes Dr 1 (13.06 KiB) Viewed 34 times
public class DoublyLinkedList<E> {
//---------------- nested Node class---------------- /** * Node of a doubly linked list, which stores areference to its * element and to both the previous and next node inthe list. */ private static class Node<E> {
/** 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 thelist
/** A reference to the subsequent node in the list*/ private Node<E> next; // reference to the subsequent node in thelist
/** * Creates a node with the given element andnext node. * * @param e the element to be stored * @param p reference to a node thatshould precede the new node * @param n reference to a node thatshould 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 (ornull if no such node). * @return the preceding node */ public Node<E> getPrev() { return prev; }
/** * Returns the node that follows this one (ornull if no such node). * @return the following node */ public Node<E> getNext() { return next; }
// Update methods /** * Sets the node's previous reference to pointto Node n. * @param p the node that shouldprecede this one */ public void setPrev(Node<E> p) { prev = p;}
/** * Sets the node's next reference to point toNode n. * @param n the node that shouldfollow 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 includingsentinels) */ private int size = 0; // number of elements inthe list
/** Constructs a new empty list. */ public DoublyLinkedList() { header = new Node<>(null, null, null); // create header trailer = new Node<>(null, header, null); // trailer is preceded by header header.setNext(trailer); // header is followed bytrailer }
// public accessor methods /** * Returns the number of elements in the linkedlist. * @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, falseotherwise */ public boolean isEmpty() { return size == 0; }
/** * Returns (but does not remove) the first element ofthe list. * @return element at the front of the list (or null ifempty) */ public E first() { if (isEmpty()) return null; return header.getNext().getElement(); // firstelement is beyond header }
/** * Returns (but does not remove) the last element ofthe list. * @return element at the end of the list (or null ifempty) */ 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) { addBetween(e, header, header.getNext()); // place just after the header }
/** * Adds an element to the end of the list. * @param e the new element to add */ public void addLast(E e) { addBetween(e, trailer.getPrev(), trailer); //place just before the trailer }
/** * Removes and returns the first element of thelist. * @return the removed element (or null if empty) */ public E removeFirst() { if (isEmpty()) return null; // nothing to remove return remove(header.getNext()); // first element is beyond header }
/** * Removes and returns the last element of thelist. * @return the removed element (or null if empty) */ public E removeLast() { if (isEmpty()) return null; // nothing to remove return remove(trailer.getPrev()); // last element is before trailer }
// private update methods /** * Adds an element to the linked list in between thegiven nodes. * The given predecessor and successor should beneighboring each * other prior to the call. * * @param predecessor node just before thelocation where the new element is inserted * @param successor node just after thelocation 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 itselement. * @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(); predecessor.setNext(successor); successor.setPrev(predecessor); size--; return node.getElement(); }
/** * Produces a string representation of the contents ofthe 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 -----------
1) Submit a public void method in the DoublyLinked List class that swaps two non adjacent (and not header and tail nodes), given the index of the elements. Copy the book's class into your own project and modify.