Linked List 구현 using class in Python (2)

맨 뒤에 노드 추가하기

class Node:
  def __init__(self, data):
    self.data = data	
    self.next = None

class LinkedList:
  def __init__(self, value):
    self.head = Node(value)

저번 포스팅에서 LinkedList를 위해 위와 같은 클래스를 만드는 것 까지 했다.

이번에는 LinkedList의 맨 뒤에 새로운 Node를 붙이는 append 함수를 만들어보자

 

how?

현재 있는 노드의 가장 맨 뒤에 새로운 값을 가진 노드를 추가하면 된다. 끝

말로는 쉽지만 그러기 위해선 먼저 가장 맨 뒤의 노드까지 이동해야 한다.

head
[3]	->	[5]	->	[7]

 

head를 변경시킬 수는 없으니 cur = self.head를 넣는다.

cur
[3]	->	[5]	->	[7]

 

이동방법은 cur = cur.next를 통해 할 수 있다.

이걸 cur.next가 None이 될 때 까지 반복시키면 맨 마지막 노드에 도달할 수 있다.

		cur
[3]	->	[5]	->	[7]

				cur
[3]	->	[5]	->	[7]

 

코드로 나타내면 다음과 같다.

class LinkedList:
  def __init__(self, value):
    self.head = Node(value)
    
  def append(self, value):
    cur = self.head
    while cur.next is not None:	# 마지막 노드는 next가 None인걸 이용
      cur = cur.next		# 끝까지 이동해서
    cur.next = Node(value)	# next로 새 노드를 연결해준다.

 

모든 노드 출력하기

위 코드를 응용하면 모든 노드의 데이터를 출력하는 것도 가능하다.

# ...생략
  def print_all(self):
    cur = self.head
    while cur is not None:
      print(cur.data)
      cur = cur.next
# ...생략

 

index번째 노드 찾기

마찬가지로 index만큼 이동해서 찾으면 된다.

# ...생략
  def get_node(self, index):
    node = self.head
    count = 0
    while count < index:
      node = node.next
      count += 1
    return node
# ...생략

 

index번째에 노드 추가하기

이번에는 원하는 위치에 노드를 추가해보자. 

예시로 [3] -> [5] -> [7]이 있는 linkedList의 인덱스가 1인 위치에 Node(11)을 추가해보려고 한다.

그림으로 그려 나타내면 위와 같다. 중요한 부분은

① 에서 추가될 노드로 이전 노드에서 next를 통해 새 노드에 연결해주는 것과

② 에서 새로 연결된 노드가 원래 자리에 있던 기존 노드에 next를 연결해주는 부분이다.

 

코드를 살펴보자

# ...생략
  def add_node(self, index, value):
    new_node = Node(value)
    
    if index == 0:	
    # 아래에 써있는 이유로 index-1 위치의 노드를 찾는 부분이 있는데 
    # index가 0일 경우는 문제가 생기므로 선처리 작업을 해줘야 한다.
      new_node.next = self.head
      self.head = new_node
      # 이 부분이 헷갈릴 수 있는데 바로 self.head = new_node를 해버리면 
      # 기존 관계가 사라지기 때문에 먼저 지정해준 뒤 진행해야 한다.
      return
      
    node = self.get_node(index - 1)	
    # 위에서 만든 get_node를 활용해 index 위치의 노드를 찾는데, 
    # 해당 위치에 새 노드를 연결하려면 이전 노드에서 해야하므로 index-1의 위치의 노드를 찾는 것
    next_node = node.next	
    # 새 노드가 연결된 후 새 노드의 next의 연결되야 하므로 잠깐 따로 저장해준다.
    node.next = new_node	# index-1 위치 다음에 새 노드 연결
    new_node.next = next_node	# 새 노드 다음에 기존 위치에 있던 노드 연결
# ...생략

주석으로 각 코드들에 대해 최대한 자세히 설명을 적어놓았으니 이해가 되지않는다면 참고하자.

 

index번째 노드 제거

이 경우도 그림으로 본다면 이해가 훨씬 쉽다.

# ...생략
  def delete_node(self, index):
    if index == 0:
      self.head = self.head.next
      return
    node = self.get_node(index - 1)
    node.next = node.next.next	
# ...생략

바로 다음다음의 노드를 바라보게 해주는 방법을 통해 쉽게 구현 가능하다.

다만, 마찬가지로 index-1인 노드를 가져오는 과정이 있으므로 index가 0일 때를 생각해 미리 처리해줘야 한다.