doubly linked list

Posted on March 21, 2014 by iamsocurious | Leave a comment

Insertion at the Rear of a Doubly-Linked List

Case 1: List is not empty

Assume that our linked list contains one or more nodes and that we have allocated a new list node using the pointer newNode. A diagram of the list might look like this:

To insert the new node at the rear of the list, we have to set three pointers: the prev pointer in newNode,\ the next pointer in the current last node in the list, and tail, which needs to be updated to point to the new last node in the list. (The next pointer in newNode has already been set to NULL by the constructor, so we don’t need to change that.) Once we’ve finished, the list should look like this:

Here is the C++ code to perform these three steps:

newNode->prev = tail;
tail->next = newNode;
tail = newNode;

The order of these steps is important. We can code Steps 1 and 2 in either order with no problems, but Step 3 must be done last. (Why?)

Case 2: List is empty

The steps above work as long as there is at least one node in the linked list. But what if the list is empty?

If we use the same steps as above:

newNode->prev = tail;
tail->next = newNode; // Since tail == NULL, this step causes a segmentation fault
tail = newNode;

To insert the new node at the rear of an empty list, we once again have to set three pointers: the prev and pointer in newNode, head, which needs to point to the new first node in the list, and tail, which needs to be updated to point to the new last node in the list. Once we’ve finished, the list should look like this:

So, for an empty list, the correct C++ code to perform these three steps is:

newNode->prev = tail; // Since tail == NULL, newNode->prev will be set to NULL as well
head = newNode;
tail = newNode;

To combine the two cases and minimize repetition of code, we can

Perform Step 1
Decide which version of Step 2 to perform based on whether or not the list is empty
Perform Step 3

Insertion at the Front of a Doubly-Linked List

The steps for insertion at the rear of a doubly-linked list and the steps for insertion at the front of a doubly-linked list are symmetric. This means that to write the code for push_front(), take the code you’ve written for push_back() and

change every occurrence of head to tail, and vice versa
change every occurrence of next to prev, and vice versa

Deletion at the Rear of a Doubly-Linked List

Case 1: List contains more than one node

Assume that our linked list contains two or more nodes:

The steps in C++ to remove the last node in the list look like this:

LNode* delNode = tail; // Save address of node to delete in a pointer
tail = delNode->prev; // Point tail at the new last node in the list
tail->next = NULL; // Set the new last node's next pointer to NULL
delete delNode;

Here’s a diagram of the list just after Step 3:

Case 2: List contains one node

The steps above work as long as there are at least two nodes in the linked list. But what if the list only contains one node?

If we use the same steps as above:

LNode* delNode = tail; // Save address of node to delete in a pointer
tail = delNode->prev; // This makes tail NULL, which is what it should be
tail->next = NULL; // Segmentation fault!
delete delNode;

Once again, this is a special case that needs to be handled a bit differently. The correct sequence of steps in this case is:

LNode* delNode = tail; // Save address of node to delete in a pointer
tail = delNode->prev; // This makes tail NULL
head = NULL; // If tail == NULL, head should be as well since the list is now empty
delete delNode;

Here’s a diagram of the list just after Step 3:

As with insertion, to combine the two cases and minimize repetition of code, we can

Perform Steps 1 and 2
Decide which version of Step 3 to perform based on whether or not the list is now empty (i.e., tail == NULL)
Perform Step 4

Deletion at the Front of a Doubly-Linked List

The steps for deletion at the rear of a doubly-linked list and the steps for deletion at the front of a doubly-linked list are also symmetric. This means that to write the code for pop_front(), take the code you’ve written for pop_back() and

change every occurrence of head to tail, and vice versa
change every occurrence of next to prev, and vice versa

http://faculty.cs.niu.edu/~mcmahon/CS241/Notes/doubly_linked.html

How does Java hashmap work?

Posted on May 8, 2012 by iamsocurious | Leave a comment

A hashmap works like this (this is a little bit simplified, but it illustrates the basic mechanism):

It has a number of “buckets” which it uses to store key-value pairs in. Each bucket has a unique number – that’s what identifies the bucket. When you put a key-value pair into the map, the hashmap will look at the hash code of the key, and store the pair in the bucket of which the identifier is the hash code of the key. For example: The hash code of the key is 235 -> the pair is stored in bucket number 235. (Note that one bucket can store more then one key-value pair).

When you lookup a value in the hashmap, by giving it a key, it will first look at the hash code of the key that you gave. The hashmap will then look into the corresponding bucket, and then it will compare the key that you gave with the keys of all pairs in the bucket, by comparing them with equals().

Now you can see how this is very efficient for looking up key-value pairs in a map: by the hash code of the key the hashmap immediately knows in which bucket to look, so that it only has to test against what’s in that bucket.

Looking at the above mechanism, you can also see what requirements are necessary on thehashCode() and equals() methods of keys:

If two keys are the same (equals() returns true when you compare them), their hashCode()method must return the same number. If keys violate this, then keys that are equal might be stored in different buckets, and the hashmap would not be able to find key-value pairs (because it’s going to look in the same bucket).
If two keys are different, then it doesn’t matter if their hash codes are the same or not. They will be stored in the same bucket, but the hashmap will use equals() to tell them apart.

http://stackoverflow.com/questions/6493605/how-does-java-hashmap-work

How HashMap works in Java

Posted on May 8, 2012 by iamsocurious | Leave a comment

HashMap works on principle of hashing, we have put () and get () method for storing and retrieving object form hashMap.When we pass an both key and value to put() method to store on HashMap, it uses key object hashcode() method to calculate hashcode and they by applying hashing on that hashcode it identifies bucket location for storing value object.
While retrieving it uses key object equals method to find out correct key value pair and return value object associated with that key. HashMap uses linked list in case of collision and object will be stored in next node of linked list.
Also hashMap stores both key+value tuple in every node of linked list.

What will happen if two different HashMap key objects have same hashcode?
They will be stored in same bucket but no next node of linked list. And keys equals () method will be used to identify correct key value pair in HashMap.

Read more: http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html#ixzz1uJEyIZJ7

Queue Code

Posted on October 31, 2011 by iamsocurious | Leave a comment

// Queue.java // demonstrates queue // to run this program: C>java QueueApp //////////////////////////////////////////////////////////////// class Queue { private int maxSize; private long[] queArray; private int front; private int rear; private int nItems; // ————————————————————– public Queue(int s) // constructor { maxSize = s; queArray = new long[maxSize]; front = 0; rear = -1; nItems = 0; } // ————————————————————– public void insert(long j) // put item at rear of queue { if (rear == maxSize – 1) // deal with wraparound rear = -1; queArray[++rear] = j; // increment rear and insert nItems++; // one more item } // ————————————————————– public long remove() // take item from front of queue { long temp = queArray[front++]; // get value and incr front if (front == maxSize) // deal with wraparound front = 0; nItems–; // one less item return temp; } // ————————————————————– public long peekFront() // peek at front of queue { return queArray[front]; } // ————————————————————– public boolean isEmpty() // true if queue is empty { return (nItems == 0); } // ————————————————————– public boolean isFull() // true if queue is full { return (nItems == maxSize); } // ————————————————————– public int size() // number of items in queue { return nItems; } // ————————————————————– } // end class Queue // ////////////////////////////////////////////////////////////// class QueueApp { public static void main(String[] args) { Queue theQueue = new Queue(5); // queue holds 5 items theQueue.insert(10); // insert 4 items theQueue.insert(20); theQueue.insert(30); theQueue.insert(40); theQueue.remove(); // remove 3 items theQueue.remove(); // (10, 20, 30) theQueue.remove(); theQueue.insert(50); // insert 4 more items theQueue.insert(60); // (wraps around) theQueue.insert(70); theQueue.insert(80); while (!theQueue.isEmpty()) // remove and display { // all items long n = theQueue.remove(); // (40, 50, 60, 70, 80) System.out.print(n); System.out.print(” “); } System.out.println(“”); } // end main() } // end class QueueApp // ////////////////////////////////////////////////////////////// Efficiency of Queues
As with a stack, items can be inserted and removed from a queue in O(1) time.

Stack Code

Posted on October 31, 2011 by iamsocurious | Leave a comment

// stack.java // demonstrates stacks // to run this program: C>java StackApp //////////////////////////////////////////////////////////////// class StackX { private int maxSize; // size of stack array private long[] stackArray; private int top; // top of stack // ————————————————————– public StackX(int s) // constructor { maxSize = s; // set array size stackArray = new long[maxSize]; // create array top = -1; // no items yet } // ————————————————————– public void push(long j) // put item on top of stack { stackArray[++top] = j; // increment top, insert item } // ————————————————————– public long pop() // take item from top of stack { return stackArray[top–]; // access item, decrement top } // ————————————————————– public long peek() // peek at top of stack { return stackArray[top]; } // ————————————————————– public boolean isEmpty() // true if stack is empty { return (top == -1); } // ————————————————————– public boolean isFull() // true if stack is full { return (top == maxSize – 1); } // ————————————————————– } // end class StackX // ////////////////////////////////////////////////////////////// class StackApp { public static void main(String[] args) { StackX theStack = new StackX(10); // make new stack theStack.push(20); // push items onto stack theStack.push(40); theStack.push(60); theStack.push(80); while (!theStack.isEmpty()) // until it’s empty, { // delete item from stack long value = theStack.pop(); System.out.print(value); // display it System.out.print(” “); } // end while System.out.println(“”); } // end main() } // end class StackApp // //////////////////////////////////////////////////////////////

The main() method in the StackApp class creates a stack that can hold 10 items, pushes 4 items onto the stack, and then displays all the items by popping them off the stack, and then displays all the items by popping them off the stack until it’s empty. Here’s the output.,

80 60 40 20

Notice how the order of the data is reversed. Because the last item pushed is the first one popped, the 80 appears first in the output. the the 80 appears first in the output.

Efficiency of Stacks
Items can be both pushed and popped from the stack implemented in the StackX class in constant O(1) time. That is, the time is not dependent on how many items are in the stack and is therefore very quick. No comparisons or moves are necessary. .

Priority Queue Code

Posted on October 30, 2011 by iamsocurious | Leave a comment

// priorityQ.java // demonstrates priority queue // to run this program: C>java PriorityQApp //////////////////////////////////////////////////////////////// class PriorityQ { // array in sorted order, from max at 0 to min at size-1 private int maxSize; private long[] queArray; private int nItems; // ————————————————————- public PriorityQ(int s) // constructor { maxSize = s; queArray = new long[maxSize]; nItems = 0; } // ————————————————————- public void insert(long item) // insert item { int j; if (nItems == 0) // if no items, queArray[nItems++] = item; // insert at 0 else // if items, { for (j = nItems – 1; j >= 0; j–) // start at end, { if (item > queArray[j]) // if new item larger, queArray[j + 1] = queArray[j]; // shift upward else // if smaller, break; // done shifting } // end for System.out.println(“j : ” + j); queArray[j + 1] = item; // insert it nItems++; } // end else (nItems > 0) } // end insert() // ————————————————————- public long remove() // remove minimum item { return queArray[–nItems]; } // ————————————————————- public long peekMin() // peek at minimum item { return queArray[nItems – 1]; } // ————————————————————- public boolean isEmpty() // true if queue is empty { return (nItems == 0); } // ————————————————————- public boolean isFull() // true if queue is full { return (nItems == maxSize); } // ————————————————————- } // end class PriorityQ // ////////////////////////////////////////////////////////////// class PriorityQApp { public static void main(String[] args) { PriorityQ thePQ = new PriorityQ(5); thePQ.insert(30); thePQ.insert(50); thePQ.insert(10); thePQ.insert(40); thePQ.insert(20); while (!thePQ.isEmpty()) { long item = thePQ.remove(); System.out.print(item + ” “); // 10, 20, 30, 40, 50 } // end while System.out.println(“”); } // end main() // ————————————————————- } // end class PriorityQApp // ////////////////////////////////////////////////////////////// The insert() method checks whether there are any items; if not, it inserts one at index 0. Otherwise, it starts at the top of the array and shifts existing items upward until it finds the place where the new item should go. Then it inserts the item and increments nItems. Note that if there’s any chance the priority queue is full, you should check for this possibility with isFull() before using insert(). The front and rear fields aren’t necessary as they were in the Queue class because, as we noted, front is always at nItems-1 and rear is always at 0. The remove() method is simplicity itself: It decrements nItems and returns the item from the top of the array. The peekMin() method is similar, except it doesn’t decre-ment nItems. The isEmpty() and isFull() methods check if nItems is 0 or maxSize, respectively.

Efficiency of Priority Queues
In the priority-queue implementation we show here, insertion runs in O(N) time, while deletion takes O(1) time.

Binary Tree Code

Posted on October 25, 2011 by iamsocurious | Leave a comment

package com.test; public class BinaryTreeExample { public static void main(String[] args) { new BinaryTreeExample().run(); } static class Node { Node left; Node right; int value; public Node(int value) { this.value = value; } } public void run() { Node rootnode = new Node(25); System.out.println(“Building tree with root value ” + rootnode.value); System.out.println(“=================================”); insert(rootnode, 11); insert(rootnode, 15); insert(rootnode, 16); insert(rootnode, 23); insert(rootnode, 79); System.out.println(); System.out.println(“preorder traversing”); System.out.println(“=================================”); printPreOrder(rootnode); System.out.println(); System.out.println(“postorder traversing”); System.out.println(“=================================”); printPostOrder(rootnode); System.out.println(); System.out.println(“inorder traversing”); System.out.println(“=================================”); printInOrder(rootnode); } // Insert Node: On a binary search tree, we insert a value v, by comparing it to the root. // If v > root, we go right, and else we go left. // We do this until we hit an empty spot in the tree public void insert(Node node, int value) { if (value > node.value) { if (node.right != null) { insert(node.right, value); } else { System.out.println(” Inserted ” + value + ” to right of node ” + node.value); node.right = new Node(value); } } else { if (node.left != null) { insert(node.left, value); } else { System.out.println(” Inserted ” + value + ” to left of node ” + node.value); node.left = new Node(value); } } } // In inorder, the root is visited in the middle. // In-Order: Traverse left node, current node, then right [usually used for binary search trees] public void printInOrder(Node node) { if (node != null) { printInOrder(node.left); System.out.println(“Traversed ” + node.value); printInOrder(node.right); } } // In preorder, the root is visted first. // Pre-Order: Traverse current node, then left node, then right node. public void printPreOrder(Node node) { if (node != null) { System.out.println(“Traversed ” + node.value); printPreOrder(node.left); printPreOrder(node.right); } } // in postorder, the root is visited last // Post-Order: Traverse left node, then right node, then current node. public void printPostOrder(Node node) { if (node != null) { printPostOrder(node.left); printPostOrder(node.right); System.out.println(“Traversed ” + node.value); } } }


Building tree with root value 25
=================================
  Inserted 11 to left of node 25
  Inserted 15 to right of node 11
  Inserted 16 to right of node 15
  Inserted 23 to right of node 16
  Inserted 79 to right of node 25

preorder traversing
=================================
Traversed 25
Traversed 11
Traversed 15
Traversed 16
Traversed 23
Traversed 79

postorder traversing
=================================
Traversed 23
Traversed 16
Traversed 15
Traversed 11
Traversed 79
Traversed 25

inorder traversing
=================================
Traversed 11
Traversed 15
Traversed 16
Traversed 23
Traversed 25
Traversed 79

http://www.roseindia.net/java/java-get-example/java-binary-tree-code.shtml

Linked Lists 9: Adding to an Empty List

Posted on October 23, 2011 by iamsocurious | Leave a comment

// returns the front of the modified list public static Node addLast(Node list, String s) { if (list == null) { return new Node(s, null); } Node temp = list; while (temp.getNext() != null) { temp = temp.getNext(); } temp.setNext(new Node(s, null); return list; } Node out side = …; outside = addLast(outside, “meow”);

Linked Lists 8: Adding to the End

Posted on October 23, 2011 by iamsocurious | Leave a comment

The following code does not work if list is null. public static void addLast(Node list, String s) { // find last node while (list.getNext() != null) { list = list.getNext(); } // list refers to the last node list.setNext(new Node(s, null)); } public static void addLast(Node list, String s) { Node prev = null; Node curr = list; while (curr != null) { prev = curr; curr = curr.getNext(); } prev.setNext(new Node(s, null)); }

Linked Lists 7: Some Subtleties

Posted on October 23, 2011 by iamsocurious | Leave a comment

public static void f(Node list) { list = …; // does not change linked list list.getNext().setData(…); // changes contents of linked list list.getNext().setNext(…); // changes structure of linked list } Node x = new Node(“a”, new Node(“b”, new Node(“c”, null))); x = x.getNext(); x.getNext().setNext(x.getNext()); x = x.getNext(); // “c” x.getNext().getNext().getData() // “c” x.getNext() == x.getNext().getNext(); // true size(x); // infinite loop

out of my memory

Category Archives: data structure

doubly linked list

Insertion at the Rear of a Doubly-Linked List

Case 1: List is not empty

Case 2: List is empty

Insertion at the Front of a Doubly-Linked List

Deletion at the Rear of a Doubly-Linked List

Case 1: List contains more than one node

Case 2: List contains one node

Deletion at the Front of a Doubly-Linked List

How does Java hashmap work?

How HashMap works in Java

Queue Code

Stack Code

Priority Queue Code

Binary Tree Code

Linked Lists 9: Adding to an Empty List

Linked Lists 8: Adding to the End

Linked Lists 7: Some Subtleties