Source of LinkedList.java

Structures and functions

class Node
class LinkedList

  1: //LinkedList.java

  3: class Node
  4: {
  5:     public int data;
  6:     public Node next;

  8:     public Node(int initialData)
  9:     {
 10:         data = initialData;
 11:         next = null;
 12:     }
 13: }

 15: class LinkedList
 16: {
 17:     private Node head;
 18:     private Node tail;

 20:     public LinkedList()
 21:     {
 22:         head = null;
 23:         tail = null;
 24:     }

 26:     public void append(Node newNode)
 27:     {
 28:         if (head == null)
 29:         {
 30:             head = newNode;
 31:             tail = newNode;
 32:         }
 33:         else
 34:         {
 35:             tail.next = newNode;
 36:             tail = newNode;
 37:         }
 38:     }

 40:     public void prepend(Node newNode)
 41:     {
 42:         if (head == null)
 43:         {
 44:             head = newNode;
 45:             tail = newNode;
 46:         }
 47:         else
 48:         {
 49:             newNode.next = head;
 50:             head = newNode;
 51:         }
 52:     }

 54:     public void printList()
 55:     {
 56:         Node node = head;
 57:         while (node != null)
 58:         {
 59:             System.out.print(node.data + " ");
 60:             node = node.next;
 61:         }
 62:         System.out.println();
 63:     }

 65:     public void insertAfter
 66:     (
 67:         Node currentNode,
 68:         Node newNode
 69:     )
 70:     {
 71:         if (head == null)
 72:         {
 73:             head = newNode;
 74:             tail = newNode;
 75:         }
 76:         else if (currentNode == tail)
 77:         {
 78:             tail.next = newNode;
 79:             tail = newNode;
 80:         }
 81:         else
 82:         {
 83:             newNode.next = currentNode.next;
 84:             currentNode.next = newNode;
 85:         }
 86:     }

 88:     public void removeAfter(Node currentNode)
 89:     {
 90:         if (currentNode == null && head != null)
 91:         {
 92:             // Special case: remove head
 93:             Node succeedingNode = head.next;
 94:             head = succeedingNode;
 95:             if (succeedingNode == null)
 96:             {
 97:                 // Last item was removed
 98:                 tail = null;
 99:             }
100:         }
101:         else if (currentNode.next != null)
102:         {
103:             Node succeedingNode = currentNode.next.next;
104:             currentNode.next = succeedingNode;
105:             if (succeedingNode == null)
106:             {
107:                 // Remove tail
108:                 tail = currentNode;
109:             }
110:         }
111:     }

113:     public void insertionSortSinglyLinked()
114:     {
115:         Node beforeCurrent = head;
116:         Node currentNode = head.next;
117:         while (currentNode != null)
118:         {
119:             Node nextNode = currentNode.next;
120:             Node position = findInsertionPosition(currentNode.data);
121:             if (position == beforeCurrent)
122:                 beforeCurrent = currentNode;
123:             else
124:             {
125:                 removeAfter(beforeCurrent);
126:                 if (position == null)
127:                     prepend(currentNode);
128:                 else
129:                     insertAfter(position, currentNode);
130:             }
131:             currentNode = nextNode;
132:         }
133:     }

135:     public Node findInsertionPosition(int dataValue)
136:     {
137:         Node positionA = null;
138:         Node positionB = head;
139:         while (positionB != null && dataValue > positionB.data)
140:         {
141:             positionA = positionB;
142:             positionB = positionB.next;
143:         }
144:         return positionA;
145:     }

147:     // Added for Stack/Queue section
148:     public int getHeadData()
149:     {
150:         return head.data;
151:     }
152: }