data structures - Query on doubly circular linked list using Java -

data structures - Query on doubly circular linked list using Java -

below code taken link, methods

next() prev() insertafter() insertbefore() , remove()

methods need fill solution.

before think of filling solution, ask, whether dlist abstract info type gets corrupted if user of dlist class passes dlistnode type object 5 above mentioned methods. because how dlist class create sure, if dlistnode type node part of list?

/* dlist.java */ bundle list; /** * dlist mutable doubly-linked list adt. implementation * circularly-linked , employs sentinel (dummy) node @ head * of list. * * not alter method prototypes in file. */ public class dlist { /** * head references sentinel node. * size number of items in list. (the sentinel node not * store item.) * * not alter next field declarations. */ protected dlistnode head; protected int size; /* dlist invariants: * 1) head != null. * 2) dlistnode x in dlist, x.next != null. * 3) dlistnode x in dlist, x.prev != null. * 4) dlistnode x in dlist, if x.next == y, y.prev == x. * 5) dlistnode x in dlist, if x.prev == y, y.next == x. * 6) size number of dlistnodes, not counting sentinel, * can accessed sentinel (head) sequence of * "next" references. */ /** * newnode() calls dlistnode constructor. utilize class allocate * new dlistnodes rather calling dlistnode constructor directly. * way, method needs overridden if subclass of dlist * wants utilize different kind of node. * @param item item store in node. * @param prev node previous node. * @param next node next node. */ protected dlistnode newnode(object item, dlistnode prev, dlistnode next) { homecoming new dlistnode(item, prev, next); } /** * dlist() constructor empty dlist. */ public dlist() { this.head = new dlistnode(integer.min_value, null, null); this.head.next = this.head; this.head.prev = this.head; this.size = 0; } /** * next() returns node next "node" in dlist. if "node" * null, or "node" lastly node in dlist, homecoming null. * * not homecoming sentinel under circumstances! * * @param node node successor sought. * @return node next "node". * performance: runs in o(1) time. */ public dlistnode next(dlistnode node) { if(node.next != this.head){ homecoming node.next; }else{ homecoming null; } } /** * prev() returns node prior "node" in dlist. if "node" * null, or "node" first node in dlist, homecoming null. * * not homecoming sentinel under circumstances! * * @param node node predecessor sought. * @return node prior "node". * performance: runs in o(1) time. */ public dlistnode prev(dlistnode node) { if(node.prev != this.head){ homecoming node.prev; }else{ homecoming null; } } /** * insertafter() inserts item in dlist next "node". * if "node" null, nothing. * @param item item inserted. * @param node node insert item after. * performance: runs in o(1) time. */ public void insertafter(object item, dlistnode node) { //your solution here /*if(node != null){ node.next = new dlistnode(item, node, node.next); node.next.next.prev = node.next; }*/ } /** * insertbefore() inserts item in dlist before "node". * if "node" null, nothing. * @param item item inserted. * @param node node insert item before. * performance: runs in o(1) time. */ public void insertbefore(object item, dlistnode node) { // solution here. } /** * remove() removes "node" dlist. if "node" null, nothing. * performance: runs in o(1) time. */ public void remove(dlistnode node) { // solution here. } /** * tostring() returns string representation of dlist. * * not alter method. * * @return string representation of dlist. * performance: runs in o(n) time, n length of list. */ public string tostring() { string result = "[ "; dlistnode current = head.next; while (current != head) { result = result + current.item + " "; current = current.next; } homecoming result + "]"; } } /* dlistnode.java */ bundle list; /** * dlistnode node in dlist (doubly-linked list). */ public class dlistnode { /** * item references item stored in current node. * prev references previous node in dlist. * next references next node in dlist. * * not alter next field declarations. */ public object item; protected dlistnode prev; protected dlistnode next; /** * dlistnode() constructor. * @param item store in node. * @param p node previous node. * @param n node next node. */ dlistnode(object i, dlistnode p, dlistnode n) { this.item = i; this.prev = p; this.next = n; } }

my question:

how dlist class create sure, whether dlistnode type node passed above mentioned methods genuine? passing node, have chance break mentioned invariants of dlist adt?

java data-structures doubly-linked-list