Task description: 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: and . is the value of the current node, and is a pointer/reference to the next node. val next val next If you want to use the doubly linked list, you will need one more attribute to indicate the previous node in the linked list. Assume all nodes in the linked list are . prev 0-indexed Implement the class: MyLinkedList https://gist.github.com/RakhmedovRS/70950a8b5d8c6669cdd270d3ef7737e1 Initializes the object. MyLinkedList() MyLinkedList Get the value of the node in the linked list. If the index is invalid, return . int get(int index) indexth -1 Add a node of value before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. void addAtHead(int val) val Append a node of value as the last element of the linked list. void addAtTail(int val) val Add a node of value before the node in the linked list. If equals the length of the linked list, the node will be appended to the end of the linked list. If is greater than the length, the node . void addAtIndex(int index, int val) val indexth index index will not be inserted Delete the node in the linked list, if the index is valid. void deleteAtIndex(int index) indexth Example 1: Input
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
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 Constraints: 0 <= index, val <= 1000 Please do not use the built-in LinkedList library. At most calls will be made to , , , and . 2000 get addAtHead addAtTail addAtIndex deleteAtIndex My thoughts: 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. https://gist.github.com/RakhmedovRS/beb76bad4c696c6ca962a46e5631d545 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. Reasoning: 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 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 as it stores the link to the head of the list. Please keep it mind, we’ll get back to it. int get(int index) head 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 https://gist.github.com/RakhmedovRS/ca3d76ae29d1210d6eb312f9350385d5 The next method in our list is it must insert value in the front of our list. This one is a bit tricky. We have 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 which will be storing provided value( ). 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 void addAtHead(int val) head Link scheme below We also have a variable which is here to store the number of elements in our list. size https://gist.github.com/RakhmedovRS/f18182ba692a76502f4444bf58410af6 https://gist.github.com/RakhmedovRS/b84d3c5758832540450b394dd69d85d2 The next method is it does almost the same thing as the previous one, the only difference is we insert our value before the of our list. void addAtTail(int val) tail https://gist.github.com/RakhmedovRS/47272129eea9dbc18b78f1591e79d3cd The next method is it must insert a value in LinkedList at a particular index which is provided as a parameter. The first node after has index 0, the next to it has index 1 and so on. void addAtIndex(int index, int val) head Our goal is to iterate to target index and insert value at that index. Let’s insert value 5 at index 1. https://gist.github.com/RakhmedovRS/c032fe01f6ac4679295c1ef1ec5c1f31 Our last method to implement is . 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. void deleteAtIndex(int index) https://gist.github.com/RakhmedovRS/4b67829babc66f0a3d1845d6017d48dd https://gist.github.com/RakhmedovRS/db7a74650045b6fe108b159525b7a579 The code above gives us the following results Also Published here

Too Long; Didn't Read

Making security fun one episode at a time

Implementing a Singly or Doubly Linked List in Java (A LeetCode Question)

Too Long; Didn't Read

Ruslan Rakhmedov

About Author

TOPICS

Languages

THIS ARTICLE WAS FEATURED IN...

Implementing a Singly or Doubly Linked List in Java (A LeetCode Question)

Too Long; Didn't Read

Ruslan Rakhmedov

About Author

TOPICS

Languages

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES