Because the array would have to shift all of the items in the array by one, and insert your new item at the beginning of the array. In this case the complexity of adding a new element to the linked list is constant O(1), but for the array the complexity would be O(n). That certainly is a hindrance, if you need to access a random element, but for our stack we only need to know the first element, and this is where the linked list shines. Which means, if you need to fetch an element from the middle of the collection, with arrays you could do it in a constant time, but with a linked list you would have to traverse the collection and search for your element, so the complexity for accessing a random element in the array would be O(n). Arrays are index based, linked lists are pointer based. If you compare a linked list with your standard array, the main difference would be in fetching the elements. If you add a new element to the beginning of the list, all you have to do is change two pointers, the ‘Head’ pointer, and point the new element to the old ‘Head’ pointer: Linked ListĪ linked list is a data structure used to represent a collection of elements in a form of, well, a list 🙂 What makes a linked list special is that every element has a pointer to the next element in the list, and if that pointer is nil, then you know you’ve reached the end of the list.Įvery element in the list has a pointer to the next element, and the list itself has a pointer to the first element of the list, called a ‘Head’:

Now we’re back where we started, with five items on the stack. If you call the pop operation, you’ll get back item six, and that item will be removed from the stack, like the following image illustrates: Now you can push another item on the stack, or you can pop an item from the stack. Now you have six items on the stack, and item five is no longer available to you, like so: You can push an item onto your stack, let’ say you want to push item six on it: Let’s say you have five items on your stack like the image below shows: Pop will return the item, and delete it from the stack, and peek will allow you to see what the item at the top of the stack is, but it will not remove it. Push will, obviously, push an item onto a stack. Some common operations on a stack are push, pop and peek. If you’re getting hundreds of mails a day, this might mean you’ll never see some of the mails that are on the bottom of your stack. The most recent mail will be shown at the top, and if you read your mails from top to bottom, you’ll read your most recent mails first. I good analogy would be your email inbox.

Which basically means, the last element that you add to the stack is the first one that you’ll pull out. Stack is a LIFO data structure ( Last In First Out).

We’ll implement it using another data structure called a ‘Linked List’, and for the sake of comparison, we will implement the same stack data structure using plain old arrays, and compare performances between the two. In this post we will examine one such structure called a ‘Stack’. In computer science there are many data structures.

Linked list stack python