All code from this tutorial can be found here.
After completing this tutorial you should be able to:
- Understand the organization of code in Go.
- Use linked lists to implement stacks in Go.
This article is going to be a short one. One you can probably read while sitting on the throne in the morning 🤣.
This tutorial borrows from a previous one on Linked Lists. Find it here, give it a read before coming back to this article.
In the previous article, we learned how to use slices to implement stacks in Go. This time around we will do the same but with Linked Lists.
A quick recap of the ops that can be done on Stacks:
- Push
- Pop
- Peek
As we have learned before, the only data point accessible on a stack is the one at the top. When using linked lists, this will represent the head of the list. And by extension, all insertion and deletion operations will be done at the start of this linked list.
A quick intro to code organization in Go
" In Go, code is organized in repositories, modules & packages." (Cited from the book Learning Go by Jon Bodner).
Repositories contain code that is to be version-controlled. In this case github.com/aahansingh/data-structures-with-go/ is our repo. I will use this repo as a reference for all examples up ahead.
A set of Packages make up a Module. In our case the repo data-structures-with-go at the time of writing this article has 4 packages: linkedlist, doublylinkedlist, circularlinkedlist and stack.
Unlike Java, where keywords such as private and public define the scope of variables in packages, Go uses a different more subtle approach. In Go, if the first letter of an identifier is uppercase, those variables, functions, interfaces, etc (pretty much anything that can be referred to via an identifier) are visible across all packages in the same module as well as other packages and modules. For example, the struct Node under the linkedlist package (here is the corresponding .go file) can be accessed anywhere in the same module as well as any other module.
But if an identifier starts with a lower case letter, it can be accessed only within the same package. For example, the fields stackSize under the stack struct in the stack package (here is the corresponding .go file) can be accessed only within the stack package(see line 53 here).
Now that we know how to import, define and use packages and modules let's get back to our stack implementation using linked lists.
The Data Structure & Operations:
The code above imports the linkedlist package. We can then use the struct Node from the linkedlist package. The top of the stack is a pointer to a Node & stackSize stores the current size of the stack. Here top is the head of the linked list.
Defining the operations on the stack is super simple:
To push to the stack we always insert elements to the start of the linked list. This way the head of the linked list will always point to the newest element pushed to the stack.
To pop from the stack we always delete elements from the start of the linked list. And to peek, we return the element that the head of the stack points to.
To check if the stack is empty all we need to do is check if the head of the linked list points to nil (since that is the zero value of the struct).
Quite simple innit m8!!!!
You should now be able to:
- Understand the organization of code in Go.
- Use linked lists to implement stacks in Go.
If you enjoyed reading this article or if it helped you in any way, a 👏 is appreciated. Do share this article with others who may be interested in the topic too.
Stay in touch with me on Linkedin and Twitter. Follow me on GitHub.