위코드 코드카타 Week5 Day4 - 연결리스트(Linked List)

문제

linked list를 만들 수 있는 MyLinkedList 클래스를 설계해봅시다.

singly linked list 로 해도 되고, doubly linked list 로 구현하셔도 됩니다.

 

해결

leetcode 유저 parkershamblin 

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None


class MyLinkedList(object):
    def __init__(self):
        self.head = None
        self.size = 0

    def addAtIndex(self, index: int, val: int) -> None:
        # 유효하지 않은 인덱스인 경우
        if index > self.size:
            return

        # 존재하는 노드가 있는 경우 current는 0번 노드
        # 존재하는 노드가 없는 경우 current는 None
        current = self.head
        # 새 노드 생성
        new_node = ListNode(val)

        # 노드를 첫머리에 넣는 경우
        if index <= 0:
            # 1개 이상 노드가 존재한다면 새로운 노드의 next가 0번째 노드를 가리키게 만듦
            # 아무 노드도 존재하지 않는다면 새로운 노드의 next가 None을 가리키게 만듦
            new_node.next = current
            # 헤드가 새로운 노드를 가리키게 만듦
            self.head = new_node
        else:
            # current가 삽입할 곳 직전 노드를 가리키게 만듦
            # 예) linkedlist.addAtIndex(4, 450)인 경우 current가 3을 가리키게 만듦
            for _ in range(index - 1):
                current = current.next 
            # 새 노드의 next가 삽입할 곳 직전 노드의 next를 가리키게 만듦
            new_node.next = current.next
            # 직전 노드의 next가 새 노드를 가리키게 만듦
            current.next = new_node

        self.size += 1

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1

        # 존재하는 노드가 있는 경우 current는 0번 노드
        # 존재하는 노드가 없는 경우 current는 None
        current = self.head

        for _ in range(0, index):
            current = current.next

        return current.val

    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)

    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.size, val)

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return

        # 존재하는 노드가 있는 경우 current는 0번 노드
        # 존재하는 노드가 없는 경우 current는 None
        current = self.head

        if index == 0:
            self.head = self.head.next
        else:
            # 삭제할 곳 직전 노드를 current가 가리키게 만듦
            for _ in range(0, index - 1):
                current = current.next
            # 삭제할 곳 직전 노드의 next가 다음다음 노드를 가리키게 만듦
            # 예) 3번 노드 삭제 시 current는 2번 노드 가리킴, 2번 노드의 next는 4번 노드 가리키게 만듦
            current.next = current.next.next

        self.size -= 1