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 |
public class LinkedList { private static class Node { int data; Node next; public Node(int data){ this.data = data; } public Node(int data, Node next){ this.data = data; this.next = next; } } private Node head, tail; private int count = 0; public int size(){ return count; } // If the LL is empty, create a new node, // that new node is head and tail. // If LL is not empty, prepend as before. public void prepend(int d){ if (head == null) tail = head = new Node(d); else head = new Node(d, head); count++; } public void append(int d){ if (head == null) tail = head = new Node(d); else tail = tail.next = new Node(d); count++; } public boolean contains(int d){ Node curr = head; while (curr != null && curr.data != d) curr = curr.next; return curr != null; } public int get(int idx){ if (idx >= count || idx < 0) throw new IndexOutOfBoundsException(); Node curr = head; for (int i = 0; i < idx; i++){ curr = curr.next; } return curr.data; } // Insert d into the linked list at index idx // Find the node *before* where the new node is // to be inserted. Create the new node and update // references as necessary. public void insert(int idx, int d){ if (idx > count || idx < 0) throw new IndexOutOfBoundsException(); if (idx == 0) prepend(d); else { Node curr = head; for (int i = 0; i < idx-1; i++){ curr = curr.next; } Node newNode = new Node(d, curr.next); curr.next = newNode; } count++; } @Override public String toString(){ String retVal = "Linked list of size: " + count + '\n'; for (Node temp = head; temp != null; temp = temp.next) retVal += temp.data + " "; /*Node curr = head; while(curr != null){ retVal += curr.data + " "; curr = curr.next; }*/ return retVal; } // Testing our LL: public static void main(String[] args){ LinkedList ll = new LinkedList(); ll.prepend(10); ll.prepend(45); ll.prepend(23); System.out.println("Contains 45? " + ll.contains(45)); System.out.println("Contains 37? " + ll.contains(37)); System.out.println(ll); ll.append(19); System.out.println(ll); System.out.println("First element: " + ll.get(0)); System.out.println("Last element: " + ll.get(3)); // System.out.println("Last element: " + ll.get(4)); ll.insert(4, 15); System.out.println(ll); } } |