Stack using double-linked list

Question

Hey. I am assigned to do Stack using double-linked list and I faced a problem. I can't link to previous element (while I had no problems using one link).

class Node
{
    Data data;
    Node previous;
    Node next;
}

class Data
{
    int     size;
    double  price;
    boolean isOnOffer;
    char    sex;
    String  brand;

    Data(int size, double price, boolean isOnOffer, char sex, String brand){
        this.size       = size;
        this.price      = price;
        this.isOnOffer  = isOnOffer;
        this.sex        = sex;
        this.brand      = brand;
    }
}

class Stack
{
    private static int sizeOfStack;
    private static Node topElement;

    public static boolean isEmpty() { return topElement == null; }

    public static void Initialize() {
        sizeOfStack = 0; 
        topElement = null; 
    }

    public static void Push(Data x) {

        Node oldElement = topElement;
        topElement = new Node();
        topElement.data = x;
        topElement.next = oldElement;
        topElement.previous = null;
        //oldElement.previous = topElement; // <----- problem here

        sizeOfStack++;
    }

    public static void Pop() {
        if (!isEmpty()){
            topElement = topElement.next;   // delete first node
            sizeOfStack--;
        }
    }

    public static void Top() {
        int size =           topElement.data.size;
        double price =       topElement.data.price;
        boolean isOnOffer =  topElement.data.isOnOffer;
        char sex =           topElement.data.sex;
        String brand =       topElement.data.brand;
        System.out.println(size + " " + price + " " + isOnOffer + " " + sex + " " + brand);
    }

    public static void Kill() { }
    public static void Print() { }


    public static void main(String[] args){

        Push(new Data(37, 155, false, 'F', "Nike"));
        Push(new Data(38, 140, true, 'F', "Reebok"));
        Push(new Data(35, 160.99, false, 'F', "Converse"));
        Push(new Data(35, 20.99, true, 'F', "Inkaras"));
        Pop();
        Pop();

        Top();
    }

}

it sound a bit like homework. If it is homework tag it. Otherwise: why are you implementing linked list by hand in java? Use ArrayList instead. — Heisenbug
– Heisenbug, Commented Apr 4, 2011 at 10:51
THere is no way of retrieving the top element. pop() should return the Data. — Manoj
– Manoj, Commented Apr 4, 2011 at 10:59
@Manoj: presumably they're just using top to print stuff at the moment — forsvarir
– forsvarir, Commented Apr 4, 2011 at 11:01

Thomas · Accepted Answer · 2011-04-04 11:12:05Z

1

//oldElement.previous = topElement; // <----- problem here

As already pointed out: if oldElement is null, you'd get a NullPointerException. Check for null before, like if(oldElement != null) { oldElement.previous = topElement; }.

Also note that the Top() method won't work for an empty stack, it would throw an NPE in the first line topElement.data....

answered Apr 4, 2011 at 11:12

Thomas

88.9k13 gold badges126 silver badges162 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

ejohansson · Accepted Answer · 2011-04-04 11:41:06Z

0

Look at the different cases:

{Stack} //Top of stack is the leftmost node

[Node(Next|Prev)]

Case: #1 "empty stack case"

{null}

Push:

[Node1(null|null)]

Case: #2 "normal case"

{[Node1(null|null)]}

Push:

[Node2(Node1|null)]

Change:

[Node1(null|null)] -> [Node1(null|Node2)]

Looking at Case: #3 we see that it is similar to case #2, no need to implement

{[Node2(Node1|null)],[Node1(null|Node2)]}

Push:

[Node3(Node2|null)]

Change:

[Node2(Node1|null)] -> [Node2(Node1|Node3)]

edited Apr 4, 2011 at 11:41

answered Apr 4, 2011 at 11:11

ejohansson

2,8821 gold badge25 silver badges32 bronze badges

Collectives™ on Stack Overflow

Stack using double-linked list

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related