707. Design Linked List

• python3

📎 Problem

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 the MyLinkedList object.
• int get(int index) Get the value of the indexth node in the linked list. If the index is invalid, return -1.
• 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.
• void addAtTail(int val) Append a node of value val as the last element of the linked list.
• 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.
• void deleteAtIndex(int index) Delete the indexth node in the linked list, if the index is valid.

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 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.

Pseudocode

0. 노드 클래스를 만든다.
1. MyLinkedList : head 노드에 아무것도 할당하지 않고 초기화.
2. get : head 노드에서 index까지 이동한다. index에 도달했을 경우 데이터를 리턴. index가 실제 리스트 길이보다 길면 -1을 리턴
3. addAtHead : 새 노드를 설정하고 head 노드를 가리킴. head 노드를 새 노드로 치환.
4. addAtTail : 새 노드를 설정하고 head 노드로부터 가장 끝 노드까지 이동해 추가.
5. addAtIndex : 새 노드를 설정하고 index까지 이동해 앞뒤 노드의 연결 사이에 들어가 추가.
6. deleteAtIndex : Index까지 이동해서 삭제한 뒤에 앞뒤 노드를 이어줌.

Code

class MyLinkedList:

    def __init__(self):
        self.head = None

    def get(self, index: int) -> int:
        count = 0
        current = self.head
        while current:
            if count == index:
                return current.data
            count+=1
            current = current.next
        
        return -1
        

    def addAtHead(self, val: int) -> None:
        new_node = Node(val)
        new_node.next = self.head
        self.head = new_node
        

    def addAtTail(self, val: int) -> None:
        new_node = Node(val)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node
       
        

    def addAtIndex(self, index: int, val: int) -> None:
        new_node = Node(val)
        
        
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return

        current = self.head
        count = 0

        while current:
            if count == index - 1:
                new_node.next = current.next
                current.next = new_node
                return
            current = current.next
            count+=1
        
    def deleteAtIndex(self, index: int) -> None:

        if self.head is None:
            return

        if index == 0:
            self.head = self.head.next

        current = self.head
        count = 0

        while current:
            if count == index -1:
                if current.next is None:
                    return
                current.next = current.next.next
                return 
            count+=1
            current = current.next

        return


class Node:
    def __init__(self, data):
        self.data = data  # 노드가 저장하는 데이터
        self.next = None  # 다음 노드를 가리키는 포인터


# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

Result