linked list stack in java

Question

I am attempting to implement a linked list style stack in Java (without using the built in obvious ways). The push operation is straightforward, but the pop operation is vexing. It is clear to me that it would be useful to return the "popped" value to the caller, and also adjust the linked list at the same time, but this does not seem to work.

public class ListElement {

/* constructor */
public ListElement(Integer data) {
    value = data;
}

/* next pointer and the data */
private ListElement next;
private Integer value;

/* gets the next element */
public ListElement getNext() {
    return next;
}

/* gets the data */
public Integer getValue() {
    return value;
}

/* sets the next element */
public void setNext(ListElement elem) {
    next = elem;
}

/* sets the data */
public void setValue(Integer data) {
    value = data;
}

/* prints out the list */
public void printList(ListElement head) {
    String listString = "";
    ListElement elem = head;
    while (elem != null) {
        listString = listString + elem.getValue().toString() + " ";
        elem = elem.getNext();
    }
    System.out.println(listString);
}

/* inserting at the front */
public ListElement push(ListElement head, Integer data) {
    ListElement elem = new ListElement(data);
    elem.setNext(head);
    return elem;
}

/* pop the first element */
public Integer pop (ListElement head){
    Integer popped = head.getValue();
    head = head.getNext();

    return popped;
}

 public static void main(String[] args) {



    System.out.println("Constructing List with 2 ...");
    ListElement myList = new ListElement(2);
    myList.printList(myList);

    System.out.println("Adding 1 to beginning ...");
    myList = myList.push(myList, 1);
    myList.printList(myList);

    System.out.println("Adding 0 to beginning ...");
    myList = myList.push(myList, 0);
    myList.printList(myList);

    System.out.println("Pop ...");
    Integer popped =  myList.pop(myList);
    System.out.println("Value is " + popped);
    myList.printList(myList);
      }

 }

The pop function does not work, it returns the value from the head node, but as noted below, I am apparently simply modifying the local variable of "head" so the first node isn't removed. It could be done in two functions I imagine, so that the first one "gets" the value, and the second function "removes" the first node now that the value is saved, but this isn't as elegant of a solution as I would like. — user1527739
– user1527739, Commented Nov 11, 2013 at 5:16
All four answers below were exactly what was needed. The separation of elements from a stack/list object solved all of the issues and made the implementation very easy. — user1527739
– user1527739, Commented Nov 11, 2013 at 20:43

rolfl · Accepted Answer · 2013-11-11 05:03:05Z

Typically in a structure like yours you have two classes, one is the ListElement, and the other is the List. I think the names StackElement and Stack would be better, but, moving on....

The problem is that Java is in your pop method, as you suspect:

/* pop the first element */
public Integer pop (ListElement head){
    Integer popped = head.getValue();
    head = head.getNext();
    return popped;
}

but also in the main method:

System.out.println("Pop ...");
Integer popped =  myList.pop(myList);

The problem here is that you are expecting myList to be updated with the revised value head.getNext() from in the pop() method.

This will not happen.... Java creates a different 'reference' to the myList when you call pop() and the line head = head.getNext() does not change the myList ourside the pop().

This situation is typically solved with a second class, call it 'List' (or as I say, should be Stack)...

public class Stack() {
    private StackElement head = null;
    public push(Integer value) {
        StackElement topush = new StackElement(value);
        topush.setNext(head);
        head = topush;
    }
    public Integer pop() {
        StackElement topop = head;
        if (head != null) {
            head = topop.getNext();
            return topop.getValue();
        }
        return null;
    }
}

Then, in your main method, you should use this new Stack class:

Stack stack = new Stack();
stack.push(2);
....

mattdee123 · Accepted Answer · 2013-11-11 04:56:49Z

1

Generally with a Linked List like this you want a Header or LinkedList class which contains a reference to the top of the stack.

It would have one field ListElement top and the functions pop and push.

push is, as you might expect, just a matter of setting start to a new ListElement and that element's next equal to the old start.

pop is just returning the start element's value and setting start = start.getNext() thus removing the top.

answered Nov 11, 2013 at 4:56

mattdee123

2131 gold badge5 silver badges11 bronze badges

Comments

Henry · Accepted Answer · 2013-11-11 04:57:53Z

1

You aren't modifying myList when you say

head = head.getNext();

You are simply modifying a local variable in the pop method.

My favourite solution would be to separate a 'List' and an 'Element' totally, as in, two separate files. Then things should start making more sense.

List

head (of type Element)

Element

next (of type Element)
value (of type Integer)

answered Nov 11, 2013 at 4:57

Henry

6,6402 gold badges26 silver badges30 bronze badges

Comments

yohm · Accepted Answer · 2013-11-11 05:28:29Z

You can find the right implementation here.

What's wrong in your code is:

/* pop the first element */
public Integer pop (ListElement head){
    Integer popped = head.getValue();
    head = head.getNext();
    return popped;
}

You modify the head element which is only local to your function.

You need to split your code in two classes:

ListElement: will only contain the value/next info,

public class ListElement {
     ListElement next;
     Integer value;
}

LinkedStack: will only contain at least stack functions (push/pop), and a reference to the first ListElement of your stack. It's this reference that need to be updated while calling pop function.

public class LinkedStack {

     private ListElement first;

     public void push(Integer item) {
         ListElement oldfirst = first;
         first = new ListElement();
         first.value= item;
         first.next = oldfirst;
     }


     public Integer pop() {
         Integer item = first.value;      
         first = first.next;           
         return item;                 
     }
}

Collectives™ on Stack Overflow

linked list stack in java

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related