Design Linked List
leetcode: https://leetcode.com/problems/design-linked-list/
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: 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:
MyLinkedList()Initializes theMyLinkedListobject.int get(int index)Get the value of theindexthnode in the linked list. If the index is invalid, return-1.void addAtHead(int val)Add a node of valuevalbefore 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 valuevalas the last element of the linked list.void addAtIndex(int index, int val)Add a node of valuevalbefore theindexthnode in the linked list. Ifindexequals the length of the linked list, the node will be appended to the end of the linked list. Ifindexis greater than the length, the node will not be inserted.void deleteAtIndex(int index)Delete theindexthnode in the linked list, if the index is valid.
Idea:
**solution **
Step1: create the class of ListNode, include field and constructors
Step2: define the field and define the size of list and make the first node is dummy node in the MyLinkedList.
Step3: in the get method, if the target index <0 or the index >=the size of the list, it means the target index isn’t in the list. create the current index and start from the dummy node, travser unitl make the current node move to the target node, because the head is dummy node, so make the loop end until the target index
Step4: in the addAtHead method, set the index from the dummy node to traverse the list, then set newnode point to the original head node firstly, because if make dummy node point to newnode firstly, then the new node can’t point to original head node.
Step5: in the addAtTail method, traverse the list, until the current element’s next node is null, then add the new node.
Step6: in the addAtIndex method, because it starts from dummy node, so the index > size, it can’t add element, but when it equal to the size, it can add the new element by making the last node point to new node.
when need add the element, we need to make the current index move to the previous node of targe.make the new node point to the original next node firstly in case it cna’t find the next node
Step7: In the deleteAtIndex method, when it equal to size , there is no next target element to delete.when need delete the element, we need to make the current index move to the previous node of target
Code:
class ListNode {
int val;
ListNode next;
ListNode(){}
ListNode(int val) {
this.val=val;
}
ListNode(int val, ListNode next) {
this.val = val; this.next = next;
}
}
class MyLinkedList {
int size;
ListNode dummy;
public MyLinkedList() {
size = 0;
//set the listnode and include the dummy node
dummy = new ListNode(0);
}
public int get(int index) {
//if index <0 or the index >=the size of the list
if (index < 0 || index >= size) {
return -1;
}
//set the index to traverse the list
ListNode current = dummy;
//travser unitl make the current node move to the target node, because the head is dummy node, so make the loop end until the target index
while(index>=0){
current = current.next;
index--;
}
return current.val;
}
public void addAtHead(int val) {
//we set the dummy node as virtual head in the field
//set the index to traverse the list
ListNode current = dummy;
ListNode newnode = new ListNode(val);
//set newnode point to the original head node firstly//because if make dummy node point to newnode firstly, then the new node can't point to original head node
newnode.next = current.next;
current.next = newnode;
size++;
}
public void addAtTail(int val) {
//set the index to traverse the list
ListNode current = dummy;
ListNode newnode = new ListNode(val);
//get the last node's poisition
while(current.next != null){
current = current.next;
}
//make the last node point to the new node, and new node will point to null.
current.next = newnode;
size++;
}
public void addAtIndex(int index, int val) {
//because it starts from dummy node, so the index > size, it can't add element, but when it equal to the size, it can add the new element by making the last node point to new node
if(index < 0 || index > size){
return;
}
ListNode newnode = new ListNode(val);
//set the index to traverse the list
ListNode current = dummy;
//when need add the element, we need to make the current index move to the previous node of target
while(index>0){
current = current.next;
index--;
}
//make the new node point to the original next node firstly in case it cna't find the next node
newnode.next = current.next;
current.next = newnode;
size++;
}
public void deleteAtIndex(int index) {
// when it equal to size , there is no next target element to delete
if(index < 0 || index >= size){
return;
}
//set the index to traverse the list
//when need delete the element, we need to make the current index move to the previous node of target
ListNode current = dummy;
while(index > 0){
current = current.next;
index--;
}
current.next = current.next.next;
size--;
}
}
/**
* 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);
*/