Monday, May 11, 2009

Queue Using Double Linked List

This post is the continue of my previous post, and it is the java version of my senior post about queue using double link list, he use C, it implementing the data structure book by yedidyah langsam and andrew s. tanenbaum's book, a subject in bachelor of computer science.

In case in my senior post there is a comment that asked about double linked list, I want to describe about double linked list on my own word. it's a data structure which each object has three components:
- value, information that object had, it can be integer, or some other things, just like array of integer, or array of other things
- link to object in front of it. which is the same object type
- link to object in previous of it.

the head (the most front of list) did not have link to front object, and the rear did not have link to previous object, if both of those object have links, it called circular doubly linked list. fiuhhh feels like lecture when I write it, and I think I am a good lecture ^_^

By the way after I run the program which is the java version of my senior program, in case there's plenty example of double link list on net such as from java2s, I guess there still a question for my senior algorithm, I already capture the console of java version, and I think that program is not too queueing as properly.

Queue is just like when we want to buy ticket at the XII cinema, the first body in the head (front) will get his ticket first and then out from the list (FIFO). While stack is just like the order of oreo cake in a tuppleware, we put oreo one by one in one of thin tuppleware, and then we take out one by one also, the last oreo we put, the first one we take and eat with a glass of milk (LIFO).

When I run the program and then I insert the list in order like 10, 20, 30, and so on. The head (front) of the list it should be 10, the first one, not the last one, but when we choose to view the list, it say that 10 is the rear, and I think that the first mistake. The second mistake is when we choose Delete Front, It will delete the last input, I think it also a mistake, in the queue of XII ticketing, the Front is the first person in the line, so he/she is the first person will get the ticket, not the last one.

I will tell my senior about this mistake, and this is the full code of the program, just copy paste and run it in your environment as you want:

package stack.queue;

import java.util.Scanner;

class Node {
Node previous;
int info;
Node next;

public Node(int d) {
info = d;

public class QueueUsingDLL {
public static void main(String[] args) {
Scanner scanner = new Scanner(;

Node newNode = null;
Node head = null;
Node tail = null;
Node tempNode = null;

int choice = 0;
do {
System.out.println("1. Insert Front\t2. View\t3. Search\t4. Delete Front\t5. Exit");
System.out.print("Please Choose Menu : ");
choice = scanner.nextInt();
switch (choice) {
case 1:
System.out.print("Data entry: ");
int data = scanner.nextInt();
System.out.println("You're entering " + data);
newNode = new Node(data);
if (head == null) {
head = newNode;
tail = newNode;
} else { = head;
head.previous = newNode;
head = newNode;
case 2: // view
System.out.print("From HEAD: ");
tempNode = head;
while (tempNode != null) {
System.out.print( + " ");
tempNode =; // move to back
System.out.print("\nFrom TAIL: ");
tempNode = tail;
while (tempNode != null) {
System.out.print( + " ");
tempNode = tempNode.previous; // move to front
case 3: // search
System.out.print("Searching number: ");
int search = scanner.nextInt();
tempNode = head;
while ((tempNode != null) && ( != search)) {
tempNode =;
if ((tempNode != null) && ( == search)) {
System.out.println("Data found");
} else {
System.err.println("Data not found");
case 4: // delete front
// tempNode = head;
head =;
if (head != null) {
head.previous = null;
System.out.println("Head deleted");
if (head == null)
tail = null;
case 5:
} while (choice != 5);
System.err.println("Program terminated");


No comments: