Skip to main content

Creating a linked list

 I'm working my way through the mini courses on LeetCode to understand data structures and algorithms better. I am currently on linked lists. After a few slides, I was tasked with creating a linked list. I had no idea what to do and was stuck on this problem for days. I would look at it for a bit, not know what to do, and try to work on something else, and not be able to focus on that something else because I didn't know what to do about the linked list. Meh! It was a long 3-4 days. I finally figured it out and I have to say I feel very pleased with myseld :D 

Step 1: Define a node class and a linked list class. 

Each node has a value and a pointer to the next node. There is just a single pointer here because I chose to create a singly linked list. You can also have a pointer in the reverse direction point at the previous node. That would be a doubly linked list. I also had to define my actual linked list which held the value for the head node. 


Step 2: Create a get method to get the value at a particular "index". 

I say "index" because, of course, a linked list doesn't actually have an index. What was meant was to get the index-th node in the linked list. In the problem, we are told to return -1 if a node at that "index" doesn't exist. Otherwise, the value of the node is returned. I traversed the list until I reached the index-th node and returned it. 

get method in the class MyLinkedList




Step 3 : Create a method to add a node at the head

Add a head. I think this is pretty self explanatory. An edge case I had to keep in mind - empty linked lists.

addAtHead method in the class MyLinkedList

Step 4: Add a node to the tail of the list

The edge case on this was interesting. An empty list. Which meant, that really, I was just adding a head. So that's what I did. If the list was empty, I called the addAtHead method and let it do the work of adding the node.

addAtTail method in the class MyLinkedList

Step 5: Add a node at a particular index

This took up most of my time. And a large part of it was due to me misreading the requirements. I misinterpreted it and could not understand why they wanted me to do something so ridiculous and at odds with itself. I finally realised that the only ridiculous one was me. I really did want to kick myself. Once I figured out what they were asking me to do, it was fairly smooth sailing.

addAtIndex method in the class MyLinkedList





Step 6: Delete a node at a particular "index"

Again I had to traverse the list till I reached the node to be excised. This time though, I had to stop just before the index-th node so that I can point the node before the excision to the node after the excision.

deleteAtIndex method in the class MyLinkedList

All in all, I'm pretty pleased that I figured it out. Though I can't say I like my code. I'm going to spend some time to clean it up and improve it if I can.


Labels:

Comments

Post a Comment

Popular posts from this blog

Snakes and ladders

I've started on my Python course. So far, the code has been familiar because the first few basic codes are similar to Javascript. And then modules happened. Confusion and despair! What is the world is 'if __name__ == "__main__": ' and why must I reach this section of my course on a public holiday when none of the instructors are in :( Stack overflow to the rescue, providing me a lifeline while I was drowning in a pit of serpents. I feel eternally indebted to a particular Mr Fooz.  Picture from  here From my understanding, when the Python interpreter reads a source file, it first sets the variable __name__ and then it executes all the code in the file. If that particular file that you are running(i.e. your module) is the main program, the interpreter will assign '__name__ = "__main__" '. Thereafter, any code in the aforementioned 'if' statement is run. If you have, instead, imported a module, the interpreter assigns '__name__ ...
Post a Comment
Read more

I gotta feeling...

I've been helping a colleague with his portfolio site. He's making it retro video game themed at my suggestion. He found an interesting pixelated font called arcade classic  and used it for the headings on his page. Unfortunately, some of the letters almost overlapped, making it not quite readable. Before letter spacing I looked into typography ages ago and learnt about letter and word spacing and wondered if that was something that I could fiddle with using CSS. Turns out it is a property you can customise. I opened up Chrome Dev tools and added 3 pixels of letter spacing and it looked so much better. And there's letter spacing too, so that's pretty neat.  After letter spacing Can't say CSS is my favourite thing ever but it's always nice to learn something new in unexpected ways.
Post a Comment
Read more

Fizzbuzz

I was today years old when I found out what fizzbuzz was. Yes, I'm late to the party. I was in an interview where the interviewer mentioned that ordinarily they would ask interviewees in for a round of fizzbuzz challenges, as I know. Actually sir, no, I don't know 👀 But he sounded so certain that I must surely know what it is that I was afraid to say anything so I did what I always do when I panic. Look right back saying not a word. I googled this mysterious fizzbuzz problem:  It looks pretty easy. I don't think he meant this actual problem, but problems like this. Because this problem is way too easy to be an actual problem someone asks in an interview. I decided to work on it for fun:  Yup. Super easy. I wish this is all I were asked in an interview 😄 
Post a Comment
Read more