파이썬 | 링크드 리스트 구현하기 (Prepend, Pop First, Get, Set) - 3

2024.09.23 - [computer science/python] - 파이썬 | 링크드 리스트 구현하기 (Constructor, Append, Pop) - 2

파이썬 | 링크드 리스트 구현하기 (Constructor, Append, Pop) - 2

전 글에서 컨스트럭터, Append, Pop 메서드에 대해서 공부해 보았습니다. 이번 글에서는 링크드 리스트의 Prepend, Pop First, Get, Set 메서드에 대해 살펴보겠습니다. 

 

Prepend

Prepend는 새 노드를 리스트의 맨 앞에 삽입하는 기능을 하며, 리스트의 첫 번째 노드를 변경하게 됩니다. 이 메서드를 구현할 때, 리스트가 비어 있지 않는 경우와 비어 있는 경우를 고려해야 합니다.

def prepend(self, value):
    # create new node
    new_node = Node(value)

    # add Node to beginning
    # case 1: empty list
    if self.length == 0:
        self.head = new_node
        self.tail = new_node
    else:
        # case 2: list is not empty
        new_node.next = self.head  # 새로운 노드가 기존 헤드를 가리킴
        self.head = new_node        # 새로운 노드를 헤드로 설정

    self.length += 1  # 리스트 길이를 1 증가시킴
    return True

 

Pop First

pop_first 메서드는 링크드 리스트의 첫 번째 노드를 제거하고 반환하는 역할을 합니다.

def pop_first(self):
    if self.length == 0:  # 리스트가 비어 있는지 확인
        return None  # 리스트가 비어 있으면 None 반환

    temp = self.head  # 현재 헤드 노드를 temp에 저장
    self.head = self.head.next  # 헤드를 다음 노드로 이동
    temp.next = None  # 제거된 노드의 next를 None으로 설정해 연결 끊기
    self.length -= 1  # 리스트 길이를 1 감소

    if self.length == 0:  # 리스트 길이가 0이면 tail도 None으로 설정
        self.tail = None

    return temp  # 제거된 첫 번째 노드를 반환

리스트의 길이가 0, 즉 비어 있는 경우 더 이상 제거할 노드가 없으므로 None을 반환하여 메서드를 종료합니다.

리스트가 비어 있지 않은 경우 중, 2 개 이상의 노드를 가진 경우를 살펴봅시다.

여기서 self.head는 1, self.tail은 3을 가리키고 있습니다. 먼저 self.head를 temp에 저장합니다.

이후 self.head는 그다음 노드인 2를 가리키도록 갱신됩니다.

반응형

temp.next를 None으로 설정해 노드 1과 리스트 간의 연결을 끊습니다. 그리고 리스트 길이를 업데이트 합니다.

리스트에 노드가 하나인 경우를 살펴봅시다. 리스트가 비어 있지 않으므로 가장 처음 if문은 실행되지 않습니다.

현재 head 노드를 temp에 저장합니다.

이후 self.head를 self.head.next로 갱신하는데, 현재 헤드인 1의 next는 None이므로 self.head는 None이 됩니다. 그 이후 리스트의 길이가 0이 되므로 tail도 None으로 설정합니다.

 

Get

get 메서드는 주어진 인덱스에 해당하는 노드의 값을 반환하는 기능을 합니다. 이 메서드는 연결 리스트의 특정 위치에 있는 노드에 접근할 수 있도록 해줍니다.

def get(self, index):
    # index가 유효한지 확인
    if index < 0 or index >= self.length:
        return None
    
    temp = self.head
    for _ in range(index):
        temp = temp.next  # 인덱스만큼 노드를 순회
    
    return temp

현재 리스트의 상태는 위와 같습니다. -1은 유효한 인덱스가 아니므로, get 메서드는 인덱스 유효성 검사를 수행하고 None을 반환합니다. 리스트의 길이가 3이므로, 유효한 인덱스는 0, 1, 2입니다. 따라서 3도 유효하지 않은 인덱스입니다. 이 경우에도 None을 반환합니다.

노드를 탐색하기 위해, temp 변수를 사용하여 self.head부터 시작합니다. 

[Note] for _ in range()
1. range(n): 0부터 n-1까지의 정수를 생성하는 함수입니다. 즉, n 번 반복할 수 있도록 합니다.
2. _: 이 변수는 반복 중에 사용되지 않음을 나타냅니다. 관례적으로 사용되며, 반복 변수의 값을 사용할 필요가 없을 때 _를 사용하여 코드의 가독성을 높입니다.

 

get(2) 메서드를 실행한다고 가정했을 때, 이 메서드는 링크드 리스트에서 인덱스 2에 해당하는 노드의 값을 반환하는 기능을 수행합니다. 

 

• 유효성 검사:
  • index가 0보다 작거나 현재 리스트의 길이보다 크거나 같으면 None을 반환합니다.
  • 현재 리스트의 길이는 3이니 인덱스 2는 유효한 인덱스입니다.
• 노드 탐색:
  • temp 변수를 self.head로 초기화합니다. 즉, temp는 처음에 헤드 노드(값 1)를 가리킵니다.
  • for _ in range(index)를 통해 0부터 1까지 반복합니다. 

• 결과 반환:
  • 마지막으로 temp를 반환합니다.

Set

set 메서드는 링크드 리스트에서 특정 인덱스의 노드 값을 수정하는 기능을 합니다. 이 메서드는 주어진 인덱스에 해당하는 노드를 찾아 해당 노드의 값을 새 값으로 업데이트합니다. 우리는 인덱스가 유효한지 아닌지를 확인해야 합니다. 유효하지 않을 시, None을 반환하고, 유효한 경우에는 주어진 인덱스의 노드를 찾아야 합니다. 그러기 위해선 get 메서드를 재사용합니다.

def set(self, index, value):
    # 주어진 인덱스에 해당하는 노드를 가져옵니다.
    temp = self.get(index)
    
    # 노드가 존재하는 경우
    if temp:
        # 해당 노드의 값을 새 값으로 업데이트합니다.
        temp.value = value
        return True  # 업데이트 성공
    return False  # 노드가 없으면 업데이트 실패

 

 

반환된 노드가 유효한 경우 (temp가 None이 아님), 해당 노드의 값을 새 값으로 변경합니다. 이 작업은 temp.value = value로 수행됩니다. 값이 성공적으로 수정되었을 경우 True를 반환하고, 노드가 존재하지 않는 경우에는 False를 반환합니다.

---

다음 포스팅에서 이어집니다.