파이썬) 더미 노드가 있는 연결 리스트 연산

이전 시간에는 연결리스트의 특정 원소를 지정해 연산을 하는 방법을 구현했었다. 이번엔 특정 원소의 바로 다음 원소를 지정해 연산을 하는 법을 알아보겠다.

 

우선 연결 리스트가 주어졌을 때 insertAfter등으로 새로운 메소드를 지정할 수 있다. 하지만 특정 원소의 바로 다음 원소를 지정할 경우, 맨 앞 원소의 삽입, 삭제 등의 연산은 이전 원소가 없기 때문에 어려움이 있다. 따라서 기존의 연결 리스트를 변형할 필요가 있다.

 

 위 연결 리스트는 head부분의 원소가 비어있는 노드이다. 이를 dummy node라고 한다. 이 경우 위 조건의 연산을 수행할 수 있게 된다. 이를 구현하기 위한 코드는 다음과 같다.

class LinkedList:

	def __init__(self):
		self.nodeCount = 0
		self.head = Node(None)
		self.tail = None
		self.head.next = self.tail

head를 비어있는 노드로 지정하고 head의 다음 노드를 tail로 지정한다. 이로 인해 더미 노드를 가지는 연결 리스트가 구현된다.

 

 

특정 원소를 참조하는 getAt은 다음과 같다.

# 더미 노드가 있는 연결 리스트의 특정 원소 참조
def getAt(self, pos):
    if pos < 0 or pos > self.nodeCount:
        return None

    i = 0
    curr = self.head
    while i < pos:
        curr = curr.next
        i += 1

    return curr
 
 # 연결 리스트의 특정 원소 참조
 def getAt(self, pos):
    if pos < 1 or pos > self.nodeCount:
        return None

    i = 1
    curr = self.head
    while i < pos:
        curr = curr.next
        i += 1

    return curr

기존의 getAt과의 차이점은 더미 노드가 있는 연결 리스트는 head인 더미 노드가 0부터 시작하므로 그에 맞게 pos의 범위를 한 단계 낯추었다는 점이다.

 

• 리스트 삽입

# 더미 노드가 있는 연결 리스트 삽입
def insertAfter(self, prev, newNode):
    newNode.next = prev.next
    if prev.next is None:
        self.tail = newNode
    prev.next = newNode
    self.nodeCount += 1
    return True


def insertAt(self, pos, newNode):
    if pos < 1 or pos > self.nodeCount + 1:
        return False

    if pos != 1 and pos == self.nodeCount + 1:
        prev = self.tail
    else:
        prev = self.getAt(pos - 1)
    return self.insertAfter(prev, newNode)

insertAfter를 새로 정의한다. 특정 원소 바로 다음 원소를 지정하는 코드이기 때문에 prev를 변수로 두게 된다.

삽입할 newNode의 next는 prev의 next가 되고, 기존 prev의 next는 삽입할 newNode가 된다. 일반적인 연결 리스트의 삽입 연산과 비슷하다.

insertAt은 pos가 올바른 범위값을 가지지 않는 경우에는 간단하게 구현할 수 있고, 그 외의 경우 insertAfter를 return하면서 코드를 구현할 수 있다.

 

• 리스트 삭제

삭제의 경우 두가지 경우가 주어진다.

- prev가 마지막 노드일 경우는 삭제할 노드가 없으므로 None을 return

- 리스트 맨 끝의 노드르 삭제할 경우는 tail의 조정이 필요

위 경우를 반영한 코드를 필자는 다음과 같이 구현했다.

# 더미 노드가 있는 연결 리스트 삭제
def popAfter(self, prev):
    curr=prev.next
    if prev.next==None:  #prev가 마지막 node일 때
        return None
    if curr.next==None: # 맨 끝 리스트를 삭제할 때
        self.tail=prev
        prev.next=None
    else:
        prev.next=curr.next       
    self.nodeCount -= 1
    return curr.data
     
def popAt(self, pos):
    if pos < 1 or pos > self.nodeCount:
        raise IndexError
    if pos == 1:
        prev = self.head
    else: 
        prev = self.getAt(pos - 1)
    return self.popAfter(prev)

popAfter를 작성할 때 curr이 지정이 안되있어서 prev.next를 이용해 지정을 해주었다. 그 뒤 prev가 마지막 node인 경우는 prev.next==None인 경우이므로 이 경우 None을 return하도록하였고, 맨 끝 리스트를 삭제하는 경우는 curr.next==None인 경우이므로 이 때 기존 리스트의 tail은 prev가 되므로 지정하고, prev.next는 삭제되므로 None으로 지정하였다.

그 외 경우는 prev.next=curr.next로 지정해 노드의 삭제를 구현하였다.

.popAt은 삽입부분의 insertAt과 같은 구성으로 작성하였다.

*위 코드는 필자가 개인적으로 작성한 것이므로 효율성이 떨어질 수 있다.

 

 

이전에 포스팅했던 기존 연결 리스트 연산과 더미 노드가 있는 연결 리스트의 연산 코드는 서로 효율성과는 아무런 관계가 없다. 연결 리스트 연산에 여러 방법도 있다는 것을 알기 위한 것이다.