Design your implementation of the linked list. You can choose to use a singly or doubly linked list.
A node in a singly linked list should have two attributes:
val is the value of the current node, and
next is a pointer/reference to the next node.
If you want to use the doubly linked list, you will need one more attribute
prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.
int get(int index)Get the value of the
indexthnode in the linked list. If the index is invalid, return
void addAtHead(int val)Add a node of value
valbefore the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
void addAtTail(int val)Append a node of value
valas the last element of the linked list.
void addAtIndex(int index, int val)Add a node of value
indexthnode in the linked list. If
indexequals the length of the linked list, the node will be appended to the end of the linked list. If
indexis greater than the length, the node will not be inserted.
void deleteAtIndex(int index)Delete the
indexthnode in the linked list, if the index is valid.
Input ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"] [, , , [1, 2], , , ] Output [null, null, null, null, 2, null, 3] Explanation MyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.addAtHead(1); myLinkedList.addAtTail(3); myLinkedList.addAtIndex(1, 2); // linked list becomes 1->2->3 myLinkedList.get(1); // return 2 myLinkedList.deleteAtIndex(1); // now the linked list is 1->3 myLinkedList.get(1); // return 3
0 <= index, val <= 1000
2000calls will be made to
I personally love tasks like this. It can be solved in many different ways that if we are to describe them you’ll be bored and tired of reading that amount of information. This task may help you to build or improve your skill of dividing tasks into smaller pieces. Again it’s an extremely important skill if you want to become a great software engineer. If you already have got experience in algorithms and data structures you could some something like this.
It’s perfectly fine to solve the problem this way but it only works when you already know how LinkedList works and you’re able to implement it from the scratch. While approach above can save you time. I suggest diving deeper and implementing our own version of LinkedList. I’m pretty sure many of you know how it works but when I ask you to implement is some of you may struggle.
I think after you read or learn something you should implement what you just learned. It’ll help you to understand how this data structure works and where it can be used. Knowledge you got will be memorized better.
As I said this task is a perfect example of where we may split a big task into smaller ones. So let’s try to understand how to do it.
Seem like we need to implement at least 5 different methods. It’s a great starting point. While having bigger picture in your head we could focus on specific subproblem which every method must solve. Let’s solve smaller problems one by one.
According to the description method
int get(int index)can receive index of element and return the element at this index if we have it in our list. Sounds pretty straightforward. We have list with elements, let’s iterate though it and keep track current index and index we’re provided. If they’re equal we found the element and can return. In all other cases we return -1. Pay attention to line 11. We use head as it stores the link to the head of the list. Please keep it mind, we’ll get back to it.
Example: we have list 1 -> 2 -> 3 -> 4 ->5
1 has index 0, 2 has index 1 and so on. If we’re given index 3 we must return 4
The next method in our list is
void addAtHead(int val) it must insert value in the front of our list. This one is a bit tricky. We have head which stores the link to the head so we want to push the next element and insert provided value right after the head. The first thing we do is create the new Link which will be storing provided value(scheme below). At the same time, we need to update the relations between existing links and the new one. Instead of using words let’s look at some pictures I hope I’ll help you to understand the concept
We also have a variable size which is here to store the number of elements in our list.
The next method is
void addAtTail(int val) it does almost the same thing as the previous one, the only difference is we insert our value before the tail of our list.
The next method is
void addAtIndex(int index, int val) it must insert a value in LinkedList at a particular index which is provided as a parameter. The first node after head has index 0, the next to it has index 1 and so on.
Our goal is to iterate to target index and insert value at that index. Let’s insert value 5 at index 1.
Our last method to implement is
void deleteAtIndex(int index) . It does almost the same thing as an insert at index, except one thing, this time we delete Link. This article is getting too big so I provide some pictures and code to make it easier to understand. Let’s delete node at index 3.
The code above gives us the following results
Also Published here