Remove Method for a Single and Double Linked List (Java) -
i struggling understand how implement remove(); both double , single linked class. have figured out how remove first node in double, not in single. first debug, problem solve single linked class, work on double after that.
here code have far single linked class.
public class singlelinkedclass<t> { private node <t> head; private node <t> tail; private int size; public singlelinkedclass() { size = 0; head = null; tail = null; } public void insertathead(t v) { //allocate new node node newnode = new node(v, head); //change head point new node head = newnode; if(tail == null) { tail = head; } //increase size size++; } public void insertattail(t v) { if(tail == null) { tail = new node(v, null); head = tail; size++; return; } node newnode = new node(v, null); tail.nextnode = newnode; tail = newnode; size++; } public t removehead() { if(head == null) { throw new illegalstateexception("list empty! cannot delete"); } t value = head.value; head = head.nextnode; size--; return value; } public void removetail() { //case 1: list empty if(head == null) { return; } //case 2: list has 1 node else if(head == tail) { head = tail = null; } else { node temp = head; while(temp.nextnode != tail) { temp = temp.nextnode; } tail = temp; tail.nextnode = null; } size--; } public boolean remove(t v) { node<t> previous = head; node<t> cursor = head.nextnode; if (head.nextnode == null) { return false; } while(cursor != tail){ if (cursor.value.equals(v)) { previous = cursor.nextnode; return true; } previous = cursor; cursor = cursor.nextnode; } return false; } public string tostring() { if (head == null) { return "the list empty!"; } string result = ""; node temp = head; while (temp != null) { result += temp.tostring() + " "; temp = temp.nextnode; } return result; } public int size() { return size; } private class node <t> { private t value; private node <t> nextnode; public node(t v, node<t> n) { value = v; nextnode = n; } public string tostring() { return "" + value; } } } here double linked class
public class doubelylinkedlist<e> { private int size; private node<e> header; private node<e> trailer; public doubelylinkedlist() { size = 0; header = new node<e>(null, null, null); trailer = new node<e>(null, null, header); header.next = trailer; } public boolean remove(e v) { //if list empty return false if(header.next == trailer){ return false; } //if v head of list remove , return true node <e> cursor = header.next; (int = 0; < size; i++) { //remove @ head if(cursor.value.equals(v)){ removeathead(); } cursor = cursor.next; } return true; } /* } */ public void insertathead(e v) { insertbetween(v, header, header.next); } public void insertattail(e v) { insertbetween(v, trailer.prev, trailer); } private void insertbetween(e v, node<e> first, node<e> second) { node<e> newnode = new node<>(v, second, first); first.next = newnode; second.prev = newnode; size++; } public e removeathead() { return removebetween(header, header.next.next); } public e removeattail() { return removebetween(trailer.prev.prev, trailer); } private e removebetween(node<e> first, node<e> second) { if (header.next == trailer)// if list empty { throw new illegalstateexception("the list empty!"); } e result = first.next.value; first.next = second; second.prev = first; size--; return result; } public string tostringbackward() { if (size == 0) { return "the list empty!"; } string r = ""; node<e> temp = trailer.prev; while (temp != header) { r += temp.tostring() + " "; temp = temp.prev; } return r; } public string tostring() { if (size == 0) { return "the list empty!"; } string r = ""; node<e> temp = header.next; while (temp != trailer) { r += temp + " "; temp = temp.next; } return r; } private static class node<t> { private t value; private node<t> next; private node<t> prev; public node(t v, node<t> n, node<t> p) { value = v; next = n; prev = p; } public string tostring() { return value.tostring(); } } } here driver
public class driver { public static void main(string[] args) { doubelylinkedlist<string> doubley = new doubelylinkedlist(); singlelinkedclass<string> single = new singlelinkedclass(); single.insertathead("bob"); single.insertathead("sam"); single.insertathead("terry"); single.insertathead("don"); system.out.println(single); single.remove("bob"); system.out.println("single remove head: " + single); /* single.remove("don"); system.out.println("single remove tail: " + single); single.remove("terry"); system.out.println("single remove inbetween: " + single); */ system.out.println(); system.out.println(); doubley.insertathead("bob"); doubley.insertathead("sam"); doubley.insertathead("terry"); doubley.insertathead("don"); system.out.println(doubley); doubley.remove("bob"); system.out.println("double remove head: " + doubley); doubley.remove("don"); system.out.println("double remove tail: " + doubley); /* doubley.remove("sam"); system.out.println("double remove inbetween: " + doubley); */ } }
in removehead moving head next, might become null. tail head too. tail should set null too.
doublylinkedlist better english doubelylinkedlist.
as homework, leave this.
Comments
Post a Comment