stack using linked list

Question

I got "segmentation error" in my code. what is wrong? thanks in advance. p.s it's a stack using linked list.

#include <iostream>
//stack using linked list
class LinkedList {
 public:
  LinkedList() : head(0), tail(0) {}
  ~LinkedList() {
    while (!empty()) pop();
    delete head;
  }
  void pop() {
    node* temp;
    temp = head;
    for ( ; temp->next_ != tail; temp = temp->next_) {
      tail = temp;   
    }
    delete temp;
    tail->next_ = 0;
  } //removes, but does not return, the top element
  int top() {
    return tail->value_;
  } //returns, but does not remove, the top element
  bool empty() {
    return head == 0;
  }
  void push(const int& value) {
    node* element = new node(value);
    if (empty()) {
      head = tail = element;
    } else {
      tail->next_ = element;
      tail = element;
    }
  } //place a new top element
 private:
  class node {
   public:
    node(const int& input) : value_(input), next_(0) {};
    int value_; //store value
    node* next_; //link to the next element
  };
  node* head;
  node* tail;
};
int main() {
  LinkedList list;
  list.push(1);
  list.push(2);
  list.push(3);
  list.pop();
  std::cout << list.top() << std::endl;
  return 0;
}

Did it occur to you that you should atleast tell where your code crashed? — Alok Save
– Alok Save, Commented Jan 28, 2012 at 7:40

Bo Persson · Accepted Answer · 2012-01-28 07:52:32Z

2

This part doesn't look right

for ( ; temp->next_ != tail; temp = temp->next_) {
    tail = temp;
}

because once you set tail to be the same as temp, temp->next != tail will always be true.

answered Jan 28, 2012 at 7:52

Bo Persson

92.9k31 gold badges153 silver badges211 bronze badges

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

1 Comment

ihm Over a year ago

it does give me the correct answer. but it says "double free or corruption"

Chethan Ravindranath · Accepted Answer · 2012-01-28 07:53:32Z

1

for ( ; temp->next_ != tail; temp = temp->next_) {
      tail = temp;   
}

The condition should have been

temp->next_ != 0

answered Jan 28, 2012 at 7:53

Chethan Ravindranath

2,0612 gold badges19 silver badges28 bronze badges

Comments

ASten · Accepted Answer · 2012-01-28 08:16:10Z

1

This method

  void pop() {
    node* temp;
    temp = head;
    for ( ; temp->next_ != tail; temp = temp->next_) {
      tail = temp;   
    }
    delete temp;
    tail->next_ = 0;
  } //removes, but does not return, the top element

must be like this:

  void pop() {
    if( head == tail )
    {
        delete head;
        head = 0;
    } 
    else
    {
        node* temp;
        temp = head;
        for ( ; temp->next_ != tail; temp = temp->next_) {
        }
        delete tail;
        temp->next_ = 0;
        tail = temp;
    }
  } //removes, but does not return, the top element

answered Jan 28, 2012 at 8:16

ASten

8141 gold badge8 silver badges23 bronze badges

Comments

akhisp · Accepted Answer · 2012-01-28 08:01:51Z

0

The problem I think is:

for ( ; temp->next_ != tail; temp = temp->next_) {
  tail = temp;   
}
delete temp;
tail->next_ = 0;

tail = temp should be after you find the temp that leads to tail (i.e. outside of the for loop). Also, temp = not the tail but the one before the tail. So probably you need:

for ( ; temp->next_ != tail; temp = temp->next_) {}
delete tail;
tail = temp;
tail->next_ = 0;

answered Jan 28, 2012 at 8:01

akhisp

6753 silver badges5 bronze badges

Comments

bartgol · Accepted Answer · 2012-01-29 00:50:47Z

0

The destructor looks buggy to me: you keep "popping" until empty() returns true, which happens when head is the null pointer. But then you can't call delete on head after the while loop is over...

I don't know if this is the issue, but I would check it.

Another humble tip: you didn't tell us where the seg fault happens... If you run your code with gdb (or if you just put a lot of "cout" in your code), you can detect the line that causes you problems.

answered Jan 29, 2012 at 0:50

bartgol

1,9132 gold badges24 silver badges33 bronze badges

Collectives™ on Stack Overflow

stack using linked list

5 Answers 5

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related