Using Sentinel Nodes to improve your Doubly Linked Lists[Technique Tuesdays]
This is a pretty handy trick to make your code easier and faster
To learn more about the newsletter, check our detailed About Page + FAQs
To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.
Recommend this publication to Substack over here
Take the next step by subscribing here
Most of you know about Linked Lists,
You’re probably not too confused with standard Doubly Linked Lists. They are very similar to their singly linked variant.
In today’s email/post, I will show you a neat little technique to squeak out a little bit of extra bit of performance in your DLL code. This technique will make your coding easier and more readable, and even improves performance. This is a darling of competitive coders. Use this to vow your interviewers in your Leetcode style interviews.
In computer programming, a sentinel node is a specifically designated node used with linked lists and trees as a traversal path terminator. This type of node does not hold or reference any data managed by the data structure.
Key Highlights
The basic idea- In normal implementations of LLs and DLLs, our head and tail values could be null. Instead, we set our head and tail to both be dummy nodes, that will mark the start and end of the list.
Uses- Primarily, doing this removes all the special cases in your DLL implementations. This makes your code much easier to read and implement. As a bonus, this will also trim some of the extra checks (for conditionals) and make your code more provably correct. This discussion on Stack Overflow elaborates on that.
Tradeoffs- Implementing this is trivial. And the simplification it allows for your code is amazing. You will use some extra memory, but this tradeoff is normally worth it.
For more details and examples about this technique check out this video-
For those of you that really want to get into it, the following is an implementation of a circular doubly linked-list, using Python. Read it and try to convert this into another language. It will be great practice.
class Node:
def __init__(self, data, next=None, prev=None):
self.data = data
self.next = next
self.prev = prev
def __repr__(self) -> str:
return f'Node(data={self.data})'
class LinkedList:
def __init__(self):
self._sentinel = Node(data=None)
self._sentinel.next = self._sentinel
self._sentinel.prev = self._sentinel
def pop_left(self) -> Node:
return self.remove_by_ref(self._sentinel.next)
def pop(self) -> Node:
return self.remove_by_ref(self._sentinel.prev)
def append_nodeleft(self, node):
self.add_node(self._sentinel, node)
def append_node(self, node):
self.add_node(self._sentinel.prev, node)
def append_left(self, data):
node = Node(data=data)
self.append_nodeleft(node)
def append(self, data):
node = Node(data=data)
self.append_node(node)
def remove_by_ref(self, node) -> Node:
if node is self._sentinel:
raise Exception('Can never remove sentinel.')
node.prev.next = node.next
node.next.prev = node.prev
node.prev = None
node.next = None
return node
def add_node(self, curnode, newnode):
newnode.next = curnode.next
newnode.prev = curnode
curnode.next.prev = newnode
curnode.next = newnode
def search(self, value):
self._sentinel.data = value
node = self._sentinel.next
while node.data != value:
node = node.next
self._sentinel.data = None
if node is self._sentinel:
return None
return node
def __iter__(self):
node = self._sentinel.next
while node is not self._sentinel:
yield node.data
node = node.next
def reviter(self):
node = self._sentinel.prev
while node is not self._sentinel:
yield node.data
node = node.prev
Courtesy Wikipedia
I created Technology Interviews Made Simple using new techniques discovered through tutoring multiple people into top tech firms. The newsletter is designed to help you succeed, saving you from hours wasted on the Leetcode grind. I have a 100% satisfaction policy, so you can try it out at no risk to you. You can read the FAQs and find out more here. Use the button below to get 20% off for upto a whole year.
Before proceeding, if you have enjoyed this post so far, please make sure you like it (the little heart button in the email/post). I also have a special request for you.
***Special Request***
This newsletter has received a lot of love. If you haven’t already, I would really appreciate it if you could take 5 seconds to let Substack know that they should feature this publication on their pages. This will allow more people to see the newsletter.
There is a simple form in Substack that you can fill up for it. Here it is. Thank you.
https://docs.google.com/forms/d/e/1FAIpQLScs-yyToUvWUXIUuIfxz17dmZfzpNp5g7Gw7JUgzbFEhSxsvw/viewform
To get your Substack URL, follow the following steps-
Open - https://substack.com/
If you haven’t already, log in with your email.
In the top right corner, you will see your icon. Click on it. You will see the drop-down. Click on your name/profile. That will show you the link.
You will be redirected to your URL. Please put that in to the survey. Appreciate your help.
In the comments below, share what topic you want to focus on. I’d be interested in learning and will cover them. To learn more about the newsletter, check our detailed About Page + FAQs
If you liked this post, make sure you fill out this survey. It’s anonymous and will take 2 minutes of your time. It will help me understand you better, allowing for better content.
https://forms.gle/XfTXSjnC8W2wR9qT9
I see you living the dream.
Go kill all and Stay Woke,
Devansh <3
To make sure you get the most out of Technique Tuesdays, make sure you’re checking in the rest of the days as well. Leverage all the techniques I have discovered through my successful tutoring to easily succeed in your interviews and save your time and energy by joining the premium subscribers down below. Get a discount (for a whole year) using the button below
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75