Implement Double Linked List from Stack with min complexity

Technology CommunityCategory: Linked ListsImplement Double Linked List from Stack with min complexity
VietMX Staff asked 1 year ago

Imagine all items are organized into two stacks, draw them facing each other where face is where you put and peek:

1,2,3,4-><-5,6,7,8

now you can move 4 to 5:

1,2,3-><-4,5,6,7,8

and 3 to 4:

1,2-><-3,4,5,6,7,8

and you can go backwards.

You may also need another two stacks so that you can traverse List via the tail:

1,2,3,4 -> <-5,6,7,8 // first pair of stacks
8,7,6,5 -> <-4,3,2,1 // second pair of stacks kept in reverse order

once current stack runs out

empty-><-1,2,3,4,5,6,7,8 // first pair of stacks is currently being traversed
empty-><-8,7,6,5,4,3,2,1 // second pair of stacks

simply switch to the second pair of stacks!

Implementation
import java.util.Stack;

class DoubleLinkedList{
	Stack<Integer> s;
	Stack<Integer> t;
	int count;
	DoubleLinkedList(){
		s = new Stack<Integer>();
		t = new Stack<Integer>();
		count = 0;
	}

	public void insertInBeginning(int data){
		while(!s.isEmpty()){
			t.push(s.pop());
		}
		s.push(data);
		count++;
	}

	public void insertAtEnd(int data){
		while(!t.isEmpty()){
			s.push(t.pop());
		}
		t.push(data);
		count++;
	}

	public void moveForward(){
		while(!t.isEmpty()){
			int temp = t.pop();
			System.out.println(temp);
			s.push(temp);
		}
	}

	public void moveBackward(){
		while(!s.isEmpty()){
			int temp = s.pop();
			System.out.println(temp);
			t.push(temp);
		}
	}

	public void delete(int data){
		while(!s.isEmpty()){
			t.push(s.pop());
		}
		while(!t.isEmpty()){
			if(t.peek() == data){
				t.pop();
				return;
			}
			else{
				s.push(t.pop());
			}
		}
	}

	public void deleteFirst(){
		while(!s.isEmpty()){
			int temp = s.pop();
			if(s.peek() == null){
				return;
			}
			t.push(temp);
		}
	}

	public void deleteLast(){
		while(!t.isEmpty()){
			int temp = t.pop();
			if(t.peek() == null){
				return;
			}
			s.push(temp);
		}
	}
}