Python으로 구현하는 Linked List (2) 단방향 Linked List

https://uding.tistory.com/105

Python으로 구현하는 Linked List (1) 간단한 단방향 Linked List

 

이전의 간단한 단방향 연결 리스트를 개선한 연결 리스트를 구현해보자

linked list는 삽입과 삭제가 유연하다는 장점이 있으므로 이러한 장점을 살리기 위해 insertAfter(prev, newNode) 및 popAfter(prev)와 같은 메소드를 구현한다.

이전과는 다르게 pos(위치) 정보를 이용하는 것이 아닌 prev(이전의 노드) 정보를 사용한다.

또한, 맨 앞의 노드인 head를 dummy node로 두어 좀 더 일반적으로 코드를 작성할 수 있도록 한다.

 

아래 사진은 맨 앞에 dummy node를 추가한 형태이다.

 

Linked List 코드 또한 head에 dummy node를 할당하고 head의 next에 tail이 오도록 조정한 형태로 바뀐다.

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

 

길이를 얻어내는 getLength 메소드는 다음과 같이 구현한다.

    def getLength(self):
        return self.nodeCount + 1

 

리스트를 순회하여 리스트의 데이터를 반환하는 traverse 메소드는 다음과 같다.

curr인 head 노드부터 순회를 시작하고 curr의 next가 None이 아닐 때까지 반복한다.

curr인 dummy head에는 값이 없으므로 curr.next로 이동한 후에 그 값을 results에 추가해준다.

    def traverse(self):
        results = []
        
        curr = self.head
        
        while curr.next:
            curr = curr.next
            results.append(curr.data)
            
        return results

 

pos 위치의 원소를 얻어내는 getAt 메소드는 다음과 같다.

    def getAt(self, pos):
        # pos가 범위를 벗어나는 경우
        if pos<0 or pos>self.nodeCount:
            return None
        
        # dummy head인 0부터 시작
        i = 0 
        curr = self.head
        
        while i<pos:
            curr = curr.next
            i+=1
            
        return curr

 

새로운 노드를 삽입하는 insertAfter 메소드를 구현해보자.

아래와 같은 그림에서 prev와 prev.next 사이에 newNode를 삽입하는 모습이다.

링크는 다음과 같이 조정해준다.

다음은 tail 뒤에 newNode를 삽입하는 경우이다.

이 때는 tail을 조정해야 한다.

완성된 insertAfter 메소드는 다음과 같다.

prev.next가 None인 경우가 tail 뒤에 newNode를 삽입하는 경우이므로 tail을 조정해 주는 부분이다.

    def insertAfter(self, prev, newNode):
        
        newNode.next = prev.next
        
        # 만약 tail 뒤에 newNode를 삽입하는 경우
        if prev.next == None:
            self.tail = newNode
            
        prev.next = newNode
        self.nodeCount += 1
        return True

 

pos를 지정해서 newNode를 삽입하는 insertAt 메소드는 다음과 같다.

먼저 pos가 범위를 벗어나는지 여부를 판단해준다.

그 다음 tail 뒤에 삽입하는 경우 prev를 getAt을 사용해 앞에서부터 찾는 것이 아니라 prev = self.tail을 통해 바로 prev를 찾아준다.

여기서 pos!=1 조건을 추가한 이유는 만약 pos가 1이고 빈 리스트여서 nodeCount가 0이 되어 pos가 0+1이 되는 경우 빈 리스트에 삽입하는 경우이다.

빈 리스트에는 dummy head만 존재하고 tail은 없으므로 prev를 tail로 하면 안 된다.

    def insertAt(self, pos, newNode):
        
        # pos가 범위를 벗어나는 경우
        if pos<1 or pos>self.nodeCount:
            return False
        
        # tail 뒤에 삽입하는 경우
        if pos!=1 and pos==self.nodeCount+1:
            prev = self.tail # prev를 바로 tail로
            
        else:
            prev = self.getAt(pos-1)
            
        return self.insertAfter(prev, newNode)

 

아래는 prev 다음의 노드를 삭제하는 popAfter 메소드이다.

아래 그림에서 prev를 통해 curr 노드를 알 수 있다.

curr 노드를 삭제하여 prev.next가 curr.next를 가리키도록 조정한다.

아래 그림은 prev가 마지막 노드인 경우 삭제할 노드가 없다.

prev가 마지막 노드인지 판단하는 방법은 prev.next가 None인 경우이다.

아래 그림은 마지막 노드를 삭제하는 경우이다.

이 경우는 curr.next가 None인지 여부를 통해 판단할 수 있다.

이 경우 tail을 조정해야 한다.

    def popAfter(self, prev):
        # curr는 삭제하려는 노드
        # prev의 다음 노드가 curr가 됨
        curr = prev.next
        
        # prev가 마지막 노드인 경우 None 리턴
        if curr == None:
            return None
        
        # 마지막 노드를 삭제하는 경우
        if curr.next == None:
            prev.next = None # prev가 마지막이므로 prev.next는 None
            self.tail = prev # tail 조정
        # 중간 노드를 삭제하는 경우
        else:
            prev.next = curr.next
            
        self.nodeCount -= 1 # 노드 개수 감소
        return curr.data

 

다음은 pos 정보를 사용해 노드를 삭제하는 popAt 메소드이다.

    def popAt(self, pos):
        
        # pos가 범위를 벗어나는 경우
        if pos<1 or pos>self.nodeCount:
            raise IndexError
        
        prev = self.getAt(pos-1)
        return self.popAfter(prev)

 

마지막으로 두 연결 리스트를 연결하는 concat 메소드이다.

    def concat(self, L):
        self.tail.next = L.head.next
        # L이 빈 리스트가 아닌 경우 tail이 존재함
        if L.tail:
            self.tail = L.tail
        self.nodeCount += L.nodeCount