VietMX Staff asked 3 years 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,8now you can move 4 to 5:
1,2,3-><-4,5,6,7,8and 3 to 4:
1,2-><-3,4,5,6,7,8and 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 orderonce 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 stackssimply 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);
}
}
}