Add to Head
by Isai Damier, Android Engineer @ Google
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 | /*************************************************************************** * Author: Isai Damier * Title: Singly Linked List * Project: geekviewpoint * Package: datastructure * * Description: A LinkedList is a data structure that allows access * to a collection of data using pointers/references. While an * array can also be defined as above, LinkedLists and arrays differ * in how they are stored in memory and in the operations they * allow. Unlike an array that must be stored in a block of memory, * the nodes of a LinkedList can be stored anywhere because each * node has a reference to the node that succeeds it. Because the * nodes are stored so loosely, inserting nodes into a LinkedList * is easy; whereas in an array, all the succeeding elements must * be shifted. Of course, insertion also means changing the size of * the array, which means creating the entire array anew. * * Perhaps the greatest beauty of LinkedList is that it allows * accessing an entire sequence of nodes using only one variable: * a reference to the first node in the sequence. * * Countless operations can be performed on LinkedLists. Following * are a few, ranging from the common to the very interesting. **************************************************************************/ public class SinglyLinkedList { Node head = null ; Node tail = null ; /**************************************************************** * Statement: * Add the given element before the head of the list * so that this element becomes the new head. * * Time Complexity of Solution: * Best = Average = Worst = O(1). ***************************************************************/ public void addToHead( int el) { head = new Node(el, head); if ( null == tail) { tail = head; } } } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | public class SinglyLinkedListTest { /** * Test of addToHead method, of class SinglyLinkedList. */ @Test public void testAddToHead() { System.out.println( "addToHead" ); int [] input = { 9 , 4 , 5 , 2 , 1 , 12 , 6 , 7 , 4 , 8 , 3 , 0 , 16 , 19 , 11 , 17 , 13 }; SinglyLinkedList linkedList = new SinglyLinkedList(); for ( int i = 0 ; i < input.length; i++) { assertEquals(i, linkedList.size()); linkedList.addToHead(input[i]); } int ndx = input.length; for (Node n = linkedList.head; null != n; n = n.next) { assertEquals(input[--ndx], n.data); } assertEquals( 0 , ndx); } } |