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

Deviants in a normal world

It's definitely been a bit since I've seen this graphy. Anyone who has learnt about standard deviation knows this graph. Standard Deviation Standard deviation shows us how spread out all the values in a set are from the mean. The higher the standard deviation, the more spread out the values are over a wider range and the flatter this curve. In a normal distribution, most values are within 1 standard deviation from the mean(the green part of the graph). Apparently NumPy can calculate standard deviation too! import numpy numSet = [ *lots of numbers* ] numSetStdDev = numpy.std(numSet) Variance The variance also indicates how spread out the values in a set are. It measures the average degree to which each value differs from the mean. variance = standard deviation ^2 import numpy numSet = [ *lots of numbers * ] numSetVar = numpy.var(numSet) Source:  https://www.w3schools.com/python/python_ml_standard_deviation.asp
Post a Comment
Read more

So long and thanks for all the fish! Part 1 of 2

I have been with the Tech Academy both as a software developer bootcamp student, as well as an employee. After my bootcamp, I was hired first as the live project instructor, and then as Live Project Director. This, I believe, gives me a unique point of view. I have absolutely no regrets and would join the bootcamp again. But there are a number of things I would do differently. What I have learnt as a former student 1. DO NOT WORK PART TIME.   I worked part-time(20-30hrs) during my bootcamp. I was up at 2.30-3.00am every day to work for several hours. I took a short nap, and then I took a 1hr bus ride down to campus. Studied for 7- 9 hours. Took a 1hr bus ride back home. Lather, rinse, repeat. I also had some family obligations. My weekends and half the summer were taken up caring for my young stepdaughter. I was completely exhausted by the end of the bootcamp and I didn't know if I could do more. Learning to program is HARD. You need to be fully focused. I am fortunate because I di...
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