GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — Java/DataStructures/Lists/DoublyLinkedList.java at master · mimibar/Java Expand file tree/ Copy pathDoublyLinkedList.javaMore file actions 248 lines (221 loc) · 6.55 KB / Copy pathDoublyLinkedList.javaFile metadata and controls248 lines (221 loc) · 6.55 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 package DataStructures.Lists; /** * This class implements a DoublyLinkedList. This is done using the classes * LinkedList and Link. * <p> * A linked list is similar to an array, it holds values. However, * links in a linked list do not have indexes. With a linked list * you do not need to predetermine it's size as it grows and shrinks * as it is edited. This is an example of a double ended, doubly * linked list. Each link references the next link and the previous * one. * * @author Unknown */ public class DoublyLinkedList { /** * Head refers to the front of the list */ private Link head; /** * Tail refers to the back of the list */ private Link tail; /** * Default Constructor */ public DoublyLinkedList() { head = null; tail = null; } /** * Constructs a list containing the elements of the array * * @param array the array whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */ public DoublyLinkedList(int[] array) { if (array == null) throw new NullPointerException(); for (int i : array) { insertTail(i); } } /** * Insert an element at the head * * @param x Element to be inserted */ public void insertHead(int x) { Link newLink = new Link(x); // Create a new link with a value attached to it if (isEmpty()) // Set the first element added to be the tail tail = newLink; else head.previous = newLink; // newLink <-- currenthead(head) newLink.next = head; // newLink <--> currenthead(head) head = newLink; // newLink(head) <--> oldhead } /** * Insert an element at the tail * * @param x Element to be inserted */ public void insertTail(int x) { Link newLink = new Link(x); newLink.next = null; // currentTail(tail) newlink --> if (isEmpty()) { // Check if there are no elements in list then it adds first element tail = newLink; head = tail; } else { tail.next = newLink; // currentTail(tail) --> newLink --> newLink.previous = tail; // currentTail(tail) <--> newLink --> tail = newLink; // oldTail <--> newLink(tail) --> } } /** * Delete the element at the head * * @return The new head */ public Link deleteHead() { Link temp = head; head = head.next; // oldHead <--> 2ndElement(head) head.previous = null; // oldHead --> 2ndElement(head) nothing pointing at old head so will be removed if (head == null) tail = null; return temp; } /** * Delete the element at the tail * * @return The new tail */ public Link deleteTail() { Link temp = tail; tail = tail.previous; // 2ndLast(tail) <--> oldTail --> null tail.next = null; // 2ndLast(tail) --> null if (tail == null) { head = null; } return temp; } /** * Delete the element from somewhere in the list * * @param x element to be deleted * @return Link deleted */ public void delete(int x) { Link current = head; while (current.value != x) {// Find the position to delete if (current != tail) { current = current.next; } else {// If we reach the tail and the element is still not found throw new RuntimeException("The element to be deleted does not exist!"); } } if (current == head) deleteHead(); else if (current == tail) deleteTail(); else { // Before: 1 <--> 2(current) <--> 3 current.previous.next = current.next; // 1 --> 3 current.next.previous = current.previous; // 1 <--> 3 } } /** * Inserts element and reorders * * @param x Element to be added */ public void insertOrdered(int x) { Link newLink = new Link(x); Link current = head; while (current != null && x > current.value) // Find the position to insert current = current.next; if (current == head) insertHead(x); else if (current == null) insertTail(x); else { // Before: 1 <--> 2(current) <--> 3 newLink.previous = current.previous; // 1 <-- newLink current.previous.next = newLink; // 1 <--> newLink newLink.next = current; // 1 <--> newLink --> 2(current) <--> 3 current.previous = newLink; // 1 <--> newLink <--> 2(current) <--> 3 } } /** * Returns true if list is empty * * @return true if list is empty */ public boolean isEmpty() { return (head == null); } /** * Prints contents of the list */ public void display() { // Prints contents of the list Link current = head; while (current != null) { current.displayLink(); current = current.next; } System.out.println(); } } /** * This class is used to implement the nodes of the * linked list. * * @author Unknown */ class Link { /** * Value of node */ public int value; /** * This points to the link in front of the new link */ public Link next; /** * This points to the link behind the new link */ public Link previous; /** * Constructor * * @param value Value of node */ public Link(int value) { this.value = value; } /** * Displays the node */ public void displayLink() { System.out.print(value + " "); } /** * Main Method * * @param args Command line arguments */ public static void main(String args[]) { DoublyLinkedList myList = new DoublyLinkedList(); myList.insertHead(13); myList.insertHead(7); myList.insertHead(10); myList.display(); // <-- 10(head) <--> 7 <--> 13(tail) --> myList.insertTail(11); myList.display(); // <-- 10(head) <--> 7 <--> 13 <--> 11(tail) --> myList.deleteTail(); myList.display(); // <-- 10(head) <--> 7 <--> 13(tail) --> myList.delete(7); myList.display(); // <-- 10(head) <--> 13(tail) --> myList.insertOrdered(23); myList.insertOrdered(67); myList.insertOrdered(3); myList.display(); // <-- 3(head) <--> 10 <--> 13 <--> 23 <--> 67(tail) --> } } |
| You are visitor 01402520 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |