• Advertisement
Sign in to follow this  

Can I use a singly linked list for stacks and queues?

This topic is 4791 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello, I've been studying my favorite data structure, the linked list, for the past few weeks and I was wondering, after reading an article on stacks and queues, if its possible to just use a singly list for both stacks and queues. From reading various articles on the two data structures a singly list seems logical to me with slight modifications of course. The insertion order would be straight forward. Whenever I push a new element I would just be appending the element to the end of the list. In the stack the tail could be the top. In a queue whenever I add new items I would just prepend the list since queues are of FIFO structure. I seriously see nothing wrong with this. Do you? [Edited by - Khaosifix on January 6, 2005 1:07:30 AM]

Share this post


Link to post
Share on other sites
Advertisement
No problem with this. In fact, I would say a singly linked list is one of the most common implementations of both of these data structures....

Where did you get the idea that this was unaccepted?

Share this post


Link to post
Share on other sites
In Ron Penton's book he used an array which makes absolutely no sense to me. Actually he had two implementations. One is a doubly list while the other was an array of stacks. Both methods seem illogical to me since doubly list take up more memory on the pointer table than a singly list.

[Edited by - Khaosifix on January 6, 2005 1:48:31 AM]

Share this post


Link to post
Share on other sites
It's fine for a queue. For a stack, you'd want a doubly-linked list. Many times people use a queue they actually want a priority queue, which is better implemented as heap with a tree structure.

Of course you CAN use a singly-linked list for a stack... but think what happens when you pop: you need to set the node before the last to have a 'next' pointer of NULL, but you can't traverse backwards, so you have to traverse the entire list to find "next-to-last".

Share this post


Link to post
Share on other sites
A pop op will flop.

Arrgh. The above post ruined my timing.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
ajas95,
I think you got it a little mixed up. For a stack a singly link list will work great. Since you are pushing and popping off of the same side of the list. However, in a queue it is a little more tricky since you need to pop off of one side and then push on two the other.

Share this post


Link to post
Share on other sites
Nah, he's right. A slist stack would grow well, but not shrink.
OP: You like lists? Nobody likes lists! ;)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
This stack with a slinked list grows and shrinks in constant time.

#include
#include

using namespace std;

template
struct Cell
{
public:
Cell(T t, Cell *lst)
{
item = t;
next = lst;
}
T item;
Cell *next;
};


template
class Stack
{
public:
Stack( T emptyValue ) { head = NULL; this->emptyValue = emptyValue; }
void push(T t)
{
Cell *h = new Cell(t, head);
head = h;
}
T pop()
{
if (head == NULL) return this->emptyValue;
Cell *ptr = head;
T t = head->item;
head = head->next;
delete ptr;
return t;
}
void display()
{
if ( empty() ) { cout next) cout item) *s = new Stack( -1 );

s->display();
s->push(1);
s->display();
s->push(2);
s->display();
s->push(3);
s->display();
s->push(4);
s->display();
s->pop();
s->display();
s->pop();
s->display();
s->pop();
s->display();
s->pop();
s->display();

system("PAUSE");

return 0;
}

-The code is a little sloppy

Share this post


Link to post
Share on other sites
Quote:
Original post by ajas95
It's fine for a queue. For a stack, you'd want a doubly-linked list. Many times people use a queue they actually want a priority queue, which is better implemented as heap with a tree structure.

Of course you CAN use a singly-linked list for a stack... but think what happens when you pop: you need to set the node before the last to have a 'next' pointer of NULL, but you can't traverse backwards, so you have to traverse the entire list to find "next-to-last".
Sorry but, Bollucks!
Khaosifix and SnprBoB86 had it absolutely correct straight off.

A singly-linked-list is perfect for both a stack and a queue (the two main uses).
With a stack you add and remove from the head. They are O(1) operations known as 'Push' and 'Pop'.
With a queue you add at the tail and remove from the head. They are O(1) operations known as 'Put' and 'Get'.
There is absolutely no reason whatsoever to use a doubly-linked-list. Doing so would be ridiculous and actually make it far LESS efficient!
This is pretty basic stuff that I'd expect most programmers to know.

You guys must have a serious caffiene deficiency today or something.[smile]
Are you going to slap yourselves on the forehead now, or do I have to post code first?

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
ajas95,
I think you got it a little mixed up.


Right, my thinking was skewed by the OP :)

For a stack if you push on to the front of a linked list it's no problem. However, I still maintain that a queue is also easy to represent with a singly-linked list... you just need to store one pointer to the last element in the list no know where to insert.

So, to the OP: Both are fine, except do your insertion the opposite way you describe.

[edit]
And to iMalc, while I respect your "There is absolutely no reason whatsoever to use a doubly-linked-list. Doing so would be ridiculous and actually make it far LESS efficient!"...

write me a swap(A, B) implementation for a singly-linked list... that works in ALL cases (where A and B are valid).

[/edit]

Share this post


Link to post
Share on other sites
Quote:
Original post by iMalc
Quote:
Original post by ajas95
It's fine for a queue. For a stack, you'd want a doubly-linked list. Many times people use a queue they actually want a priority queue, which is better implemented as heap with a tree structure.

Of course you CAN use a singly-linked list for a stack... but think what happens when you pop: you need to set the node before the last to have a 'next' pointer of NULL, but you can't traverse backwards, so you have to traverse the entire list to find "next-to-last".
Sorry but, Bollucks!
Khaosifix and SnprBoB86 had it absolutely correct straight off.

A singly-linked-list is perfect for both a stack and a queue (the two main uses).
With a stack you add and remove from the head. They are O(1) operations known as 'Push' and 'Pop'.
With a queue you add at the tail and remove from the head. They are O(1) operations known as 'Put' and 'Get'.
There is absolutely no reason whatsoever to use a doubly-linked-list. Doing so would be ridiculous and actually make it far LESS efficient!
This is pretty basic stuff that I'd expect most programmers to know.

You guys must have a serious caffiene deficiency today or something.[smile]
Are you going to slap yourselves on the forehead now, or do I have to post code first?


LMAO. Well said. Excuse my french but Ron Penton's book is a piece of crap.

Share this post


Link to post
Share on other sites
Quote:
Original post by ajas95
Quote:
Original post by Anonymous Poster
ajas95,
I think you got it a little mixed up.


Right, my thinking was skewed by the OP :)

For a stack if you push on to the front of a linked list it's no problem. However, I still maintain that a queue is also easy to represent with a singly-linked list... you just need to store one pointer to the last element in the list no know where to insert.

So, to the OP: Both are fine, except do your insertion the opposite way you describe.

[edit]
And to iMalc, while I respect your "There is absolutely no reason whatsoever to use a doubly-linked-list. Doing so would be ridiculous and actually make it far LESS efficient!"...

write me a swap(A, B) implementation for a singly-linked list... that works in ALL cases (where A and B are valid).

[/edit]


I think iMalc meant in the situation of creating a stack or queue, there would never be a reason to use a doubly-linked list. Therefore you can't swap elements in a stack or queue. but lists have their purpose, but it isn't necessary to use a doubly-linked list for making a stack or queue.

I, personally, like deques. That was more fun to make than lists, vectors, etc.

Books don't necessary tell you the more efficient way to make data structures. Especially books that are designed to introduce something. There are many ways to make a data structure. If you want it to conform to the STL though, then it limits what you can do because it requires a certain big O.

Share this post


Link to post
Share on other sites
Quote:
Quote:
Original post by nprz
[edit]
And to iMalc, while I respect your "There is absolutely no reason whatsoever to use a doubly-linked-list. Doing so would be ridiculous and actually make it far LESS efficient!"...

write me a swap(A, B) implementation for a singly-linked list... that works in ALL cases (where A and B are valid).

[/edit]


I think iMalc meant in the situation of creating a stack or queue, there would never be a reason to use a doubly-linked list. Therefore you can't swap elements in a stack or queue. but lists have their purpose, but it isn't necessary to use a doubly-linked list for making a stack or queue.

I, personally, like deques. That was more fun to make than lists, vectors, etc.
Oh I didn't realise I left it open to misinterpretation (my bad), yes the context of a stack or queue is what I meant.
Off topic, I could write a swap implementation for a singly-linked-list, but of course it is O(n), not O(1). After clearing up the misunderstanding I see no reason to post it now, as a swap is never used in a pure stack or queue.
Doubly-linked-lists are of course equally as useful, but meant for other purposes.

Rock on, Brothers...

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement