CODEWITHSUNDEEP
javaalgorithmsortingstackquicksort
Ej Hannah
Ej Hannah

Reputation: 11

What is the benefit of using a stack versus just a doubly linked list

As an assignment, I have to implement quicksort iteratively rather than recursively. In doing this, I need to use stacks. What is the benefit of using stacks in this scenario versus just a singly or doubly linked list?

Upvotes: 0

Views: 621

Answers (3)

SimoV8
SimoV8

Reputation: 1402

The stack is an interface that define a set of operations that should be defined and it can be implemented in many ways, with a linked list, a double linked list, an array, ect.(also with queues if you want, even if I don't suggest so). The definition of this set of operations limit the scope of the data structure, allowing to get better performances for the specific use case.

In general to remove an element from a linked list or an array it takes O(n) because the element you want to remove could be in any position, so you have to find it first. In a stack, implementing pop with the same data structures you can achieve O(1) because you already know where is the element to remove (it's the head in case o linked list and the last element in case of array).

Upvotes: 0

Jim Mischel
Jim Mischel

Reputation: 134005

The simple answer is expressiveness. As was pointed out in comments, you can implement a stack with a linked list. The nice thing about "using a stack" is that you don't have to worry about the details of the implementation. That is, if you just used a linked list, you'd have something like:

// push onto the stack
newNode = createStackNode(myData);
newNode.Next = root;
root = newNode;

// pop from stack
poppedNode = root;
root = root.Next;
myData = poppedNode.data;

If you use an existing Stack data structure, then you don't have to worry about the details of pushing and popping. All you have to write is:

theStack.push(myData);

or

myData = theStack.pop();

Point being that you know the Stack data structure works. And it's really difficult to goof up a call to push or pop. It's very easy to screw up code that adds things to and removes things from the head of a linked list.

Upvotes: 2

A Sdi
A Sdi

Reputation: 665

Push has O(1) and Pop has O(1) time complexity in stack while Inserting may have O(N) (the best case occurs if you add to head, O(1)) and searching has a O(N) in linkedList. Since you need to perform both add and retrive operation, it would be more expensive to utilize LinkedList

Upvotes: -1

Related Questions