It is Friday evening. It seems that the weeks are going by faster than ever. Hopefully the COVID-19 vaccine will make a huge difference all over the world and we will be able to get on with our lives.
Earlier this week, I decided to add some spice to this blog. If you are a follower you should have noticed that lately most of the problems are being solved in Java. In the near future I will be using C and C++ if such languages would provide simpler and higher performance solutions. That said, if I get a request to generate a solution in Java, I will generate a separate post.
I have been programming in C and C++ for a long time. I have developed solutions and systems using Apple, Linux, real-time OS, UNIX, and Windows platforms. Have read a few books on subject. At work I use C/C++ about 75% of the time. No matter how proficient one might be in a programming language, there are always some concepts that need to be refreshed and some that we might have missed. Not only that, but most languages are constantly evolving by adding new features and deprecating older and unsafe ones. Because of these reasons, I have ordered from Amazon the following books:
| Book | Author |
| Algorithms in C++ Part 5: Graph Algorithms | Sedgewick, Robert |
| Algorithms in C++, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching, Third Edition | Sedgewick, Robert |
| Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching | Sedgewick, Robert |
All three books should be arriving next Tuesday. I just received a message from Amazon that one of the books has already been shipped!
Earlier this morning I was browsing problems at LeetCode. I ran into LeetCode 707 Design Linked List. I had to attempt to solve the problem.
Many years ago I started developing a set of libraries in C / C++ to help developers at work concentrate on the problems at hand and not on ancillary items i.e., hash maps, linked list, stacks, and sockets, among others. I have been maintaining and enhancing the libraries which are still in use in production code.
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 and next. 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. Implement the MyLinkedList class: o MyLinkedList() Initializes the MyLinkedList object. o int get(int index) Get the value of the indexth node in the linked list. If the index is invalid, return -1. o void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. o void addAtTail(int val) Append a node of value val as the last element of the linked list. o void addAtIndex(int index, int val) Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted. o void deleteAtIndex(int index) Delete the indexth node in the linked list, if the index is valid. Constraints: o 0 <= index, val <= 1000 o Please do not use the built-in LinkedList library. o At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.
The class definition and methods seem reasonable. In my opinion I would expect methods like enqueue() and dequeue(). I just counted the methods in the queue library. There are 47 at this time. The number of class members is 11. The library does implement a doubly-linked list data structure.
What is interesting is that for the problem you can implement a single or doubly linked list. The answers would be the same. I went with doubly linked lists because in practice that is what is typically used.
class MyLinkedList {
/** Initialize your data structure here. */
public MyLinkedList() {
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
public int get(int index) {
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
public void addAtHead(int val) {
}
/** Append a node of value val to the last element of the linked list. */
public void addAtTail(int val) {
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
public void addAtIndex(int index, int val) {
}
/** Delete the index-th node in the linked list, if the index is valid. */
public void deleteAtIndex(int index) {
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/
It appears we need to implement six methods in our class. We also need to declare the class members. It seems that the requirements mandate two or three fields depending on the type of linked list we decide to implement.
LeetCode provides an example on how our code will be tested. An object will be created. Then the different methods will be called. Seems reasonable and we have seen such approach used in many problems.
I will develop this code using the Java programming language on a Windows 10 machine using the VSCode IDE. Given that I will develop the code on my machine and then copy and paste the solution to the LeetCode web site, we will need to develop some type of test scaffolding so we can collect the input data, instantiate the queue (for some reason I seem to call linked lists queues) and then call the different methods in the order specified by the input data. It makes a lot of sense to develop the code on-line using the LeetCode provided IDE. I just prefer to have the solution and test scaffolding in the same source code. You never know when you will enhance the software and will need a way to test it. Note that the test code IS NOT PART OF THE SOLUTION.
MyLinkedList,addAtHead,addAtTail,addAtIndex,get,deleteAtIndex,get 1 3 1,2 1 1 1 main <<< n: 7 main <<< cmd ==>MyLinkedList<=== main <<< cmd ==>addAtHead<=== main <<< cmd ==>addAtTail<=== main <<< cmd ==>addAtIndex<=== main <<< cmd ==>get<=== main <<< cmd ==>deleteAtIndex<=== main <<< cmd ==>get<=== main <<< MyLinkedList: null main <<< addAtHead: null main <<< addAtTail: null main <<< addAtIndex: null main <<< get: 2 main <<< deleteAtIndex: null main <<< get: 3 Expected 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 MyLinkedList,addAtHead,get,addAtHead,addAtHead,deleteAtIndex,addAtHead,get,get,get,addAtHead,deleteAtIndex 4 1 1 5 3 7 3 3 3 1 4 main <<< n: 12 main <<< cmd ==>MyLinkedList<=== main <<< cmd ==>addAtHead<=== main <<< cmd ==>get<=== main <<< cmd ==>addAtHead<=== main <<< cmd ==>addAtHead<=== main <<< cmd ==>deleteAtIndex<=== main <<< cmd ==>addAtHead<=== main <<< cmd ==>get<=== main <<< cmd ==>get<=== main <<< cmd ==>get<=== main <<< cmd ==>addAtHead<=== main <<< cmd ==>deleteAtIndex<=== main <<< MyLinkedList: null main <<< addAtHead: null main <<< get: -1 main <<< addAtHead: null main <<< addAtHead: null main <<< deleteAtIndex: null main <<< addAtHead: null main <<< get: 4 main <<< get: 4 main <<< get: 4 main <<< addAtHead: null main <<< deleteAtIndex: null Expected Output: [null,null,-1,null,null,null,null,4,4,4,null,null]
LeetCode provides one test example. You can see two examples. The second was due to a typo in a comparison. Yes, it is simpler to develop the code on the IDE provided by LeetCode.
The first input line contains a set of commands that will be called in order. After the commands we have a list of arguments. If a command does not require an argument it will not attempt to read data from the input.
Our test scaffolding seems to read the commands and display them. Then the commands appear to be called in the specified order. After executing each command our test code displays the command and the expected output. Only the get() method seems to return data.
I copied the expected output so we can easily verify if our code matches it.
/**
* !!!! NOT PART OF SOLUTION !!!!
*/
public class DesignLinkedList {
/**
* Test scafolding
*
* !!!! NOT PART OF SOLUTION !!!!
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read commands ****
String[] cmds = br.readLine().trim().split(",");
// **** number of commands ****
int n = cmds.length;
// ???? ????
System.out.println("main <<< n: " + n);
for (String cmd : cmds)
System.out.println("main <<< cmd ==>" + cmd + "<===");
// **** ****
MyLinkedList obj = null;
int val;
int index;
// **** loop once per command ****
for (String cmd : cmds) {
// **** process command ****
switch (cmd) {
case "MyLinkedList":
obj = new MyLinkedList();
// ???? ????
System.out.println("main <<< MyLinkedList: null");
break;
case "addAtHead":
// **** get value to add at head ****
val = Integer.parseInt(br.readLine().trim());
// **** ****
obj.addAtHead(val);
// ???? ????
System.out.println("main <<< addAtHead: null");
break;
case "addAtTail":
// **** get value to add at tail of queue ****
val = Integer.parseInt(br.readLine().trim());
// **** ****
obj.addAtTail(val);
// ???? ????
System.out.println("main <<< addAtTail: null");
break;
case "addAtIndex":
// **** get data to add at index ****
String[] idStrs = br.readLine().trim().split(",");
// **** ****
index = Integer.parseInt(idStrs[0]);
val = Integer.parseInt(idStrs[1]);
// **** ****
obj.addAtIndex(index, val);
// ???? ????
System.out.println("main <<< addAtIndex: null");
break;
case "get":
// **** get index ****
index = Integer.parseInt(br.readLine().trim());
// **** ****
System.out.println("main <<< get: " + obj.get(index));
break;
case "deleteAtIndex":
// **** get index ****
index = Integer.parseInt(br.readLine().trim());
// **** ****
obj.deleteAtIndex(index);
// ???? ????
System.out.println("main <<< deleteAtIndex: null");
break;
default:
System.out.println("main <<< UNEXPECTED cmd ==>" + cmd + "<==");
System.exit(-1);
break;
}
// ???? ????
// obj.headToTail();
// obj.tailToHead();
}
// **** close buffered reader ****
br.close();
}
}
The test scaffolding opens a buffered reader and uses it to read the commands. The number of commands is then displayed.
A set of three variables is defined. We will use them as LeetCode requires.
We then enter a loop in which we process a command at a time. Each command is executed within a switch. If the command requires argument(s) the test scaffold reads them from the console. The method in the class is then invoked. After the method is executed we display a message which may or may not include a returned value.
Note that after each loop we have two lines commented out. The first displays the contents of the queue from the head to tail. The second displays the contents of the queue in reverse order from the tail to the head. You can enable these methods to make sure you can follow what is going on with the queue. These methods are NOT PART OF THE SOLUTION.
When all is set and done we close the buffered reader.
/**
* Doubly-linked list class.
*
* FIFO: add at tail (prev) and remove from head (next)
* Head points to index 0 first element in the queue.
* Tail points to the last element in the queue.
* An empty queue is when next and prev point to the queue.
*
* Runtime: 7 ms, faster than 95.55% of Java online submissions.
* Memory Usage: 39.6 MB, less than 67.68% of Java online submissions.
*/
class MyLinkedList {
}
As required we are implementing the MyLinkedList class. I added a few comments so we can recall how we are going to implement the linked list.
// **** class members ****
public int val;
public MyLinkedList next;
public MyLinkedList prev;
As required by LeetCode we have three class members. In production additional fields (i.e., count, maxNodes, accessTime) might be desirable (not in this case).
/**
* Constructor(s).
*/
public MyLinkedList() {
this.next = this;
this.prev = this;
}
public MyLinkedList(int val) {
this.val = val;
}
We will have two constructors. Of course we could just use the first and then set the value in the node by hand. Having both seems to cut a millisecond or so for the set of test cases executed when you submit the code for evaluation.
/**
* Add node at head of queue.
*/
public void addAtHead(int val) {
// **** new node ****
MyLinkedList node = new MyLinkedList(val);
// **** set node references ****
node.next = this.next;
node.prev = this;
// **** set other references ****
this.next = node;
node.next.prev = node;
}
This method adds a node at the head of the queue. We create a node with the specified value. We then set the references in the node followed by the references in the queue to add the new element.
/**
* Add node at tail of queue.
*/
public void addAtTail(int val) {
// **** new node ****
MyLinkedList node = new MyLinkedList(val);
// **** set node references ****
node.next = this;
node.prev = this.prev;
// **** set other references ****
this.prev = node;
node.prev.next = node;
}
In this method we add a node to the tail of the queue. Note that a queue implements a FIFO while a stack implements a LIFO. In a queue we probably insert at the tail and remove from the head. In a stack we probably insert and remove from the head (top).
The approach is similar to the previous method.
/**
* Add a node of value val BEFORE the index-th node in the linked list.
* If index equals to the length of linked list,
* the node will be appended to the end of linked list.
* If index is greater than the length, the node will not be inserted.
*/
public void addAtIndex(int index, int val) {
// **** get to the node in the queue specified by the index ****
MyLinkedList p = this.next;
int i = 0;
for (i = 0; i < index && p != this; i++, p = p.next);
// **** check if index greater than length ****
if (p == this && i < index)
return;
// **** allocate node to insert ****
MyLinkedList node = new MyLinkedList(val);
// **** set node references ****
node.next = p;
node.prev = p.prev;
// **** set other references ****
p.prev.next = node;
p.prev = node;
}
In this method we add a node at the index and with the value specified as parameters.
We first need to locate the node at which the insertion will take place. We then check if our index is too large.
We then allocate a node with the specified value, set the references in the node and then update the queue so it links into the new node. The approach is similar yet the nodes and fields vary.
/**
* Get the value of the index-th node in the linked list.
* If the index is invalid, return -1.
*/
public int get(int index) {
// **** get to the node in the queue specified by the index ****
MyLinkedList p = this.next;
int i = 0;
for (i = 0; i < index && p != this; i++, p = p.next);
// **** check if index greater than length ****
if (p == this && i >= index)
return -1;
// **** return node value ****
return p.val;
}
This method is used to get to the node specified by an index and return the value of the node. If we exceed the length of the queue by specifying an index too large we need to return a -1; otherwise we return the value of the node.
/**
* Delete the index-th node in the linked list,
* if the index is valid.
*/
public void deleteAtIndex(int index) {
// **** get to the node in the queue specified by the index ****
MyLinkedList p = this.next;
int i = 0;
for (i = 0; i < index && p != this; i++, p = p.next);
// **** check if index greater than length ****
if (p == this && i >= index)
return;
// **** update references to exclude the node ****
p.prev.next = p.next;
p.next.prev = p.prev;
}
This method is used to delete the node at the specified index. We first attempt to locate the node. If not found we return. If the node is found we manipulate both node references that point to the node in the queue so the node is removed. We then exit the method. The garbage collector will delete the memory associated with the node.
/**
* Traverse head to tail.
*
* !!!! NOT PART OF SOLUTION !!!!
*/
public void headToTail() {
System.out.print("head->");
for (MyLinkedList p = this.next; p != this; p = p.next) {
System.out.print(p.val);
if (p.next != this)
System.out.print("->");
}
System.out.println();
}
This method is used to check if we can traverse a queue from head to tail. As we know, in a double linked list like the one we are implementing in this solution, we should be able to traverse all nodes from head to tail ending in the node representing the queue. In the node representing the queue, the next reference represents the head. This method IS NOT PART OF THE SOLUTION.
/**
* Traverse tail to head.
*
* !!!! NOT PART OF SOLUTION !!!!
*/
public void tailToHead() {
System.out.print("tail->");
for (MyLinkedList p = this.prev; p != this; p = p.prev) {
System.out.print(p.val);
if (p.prev != this)
System.out.print("->");
}
System.out.println();
}
This method is used to check if we can traverse a queue from tail to head. As we know, in a double linked list like the one we are implementing in this solution, we should be able to traverse all nodes from tail to head ending in the node representing the queue. In the node representing the queue, the prev reference represents the tail. This method IS NOT PART OF THE SOLUTION.
The last two methods traverse the queue from a start point and end when the node representing the queue is reached. Earlier in this post we indicated that an empty list is represented by the next and prev references pointing to the node representing the queue.
/**
* Return string of object.
*
* !!!! NOT PART OF SOLUTION !!!!
*/
@Override
public String toString() {
return "" + this.val;
}
This is the standard toString() method used to display a string representing a node. This method IS NOT PART OF THE SOLUTION.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all 6,739 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.
Regards;
John
john.canessa@gmail.com