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

Linked List란?

• Linked List는 링크를 통해 데이터들이 시퀀 형태로 연결된 것임
• 링크는 일종의 포인터로 각 데이터를 다른 데이터와 연결함
• node는 링크드 리스트의 구성하는 자료로 데이터와 링크(포인터)로 구성됨
• 단방향을 가지는 singly Linked List와 양방향을 가지는 doubly Linked List로 구성됨

 

Linked List 구현하기

1. 간단한 단방향 Linked List

먼저 노드(node)는 데이터와 링크(next)로 구성되며 class로 구현한다.

이미지 링크: https://realpython.com/linked-lists-python/

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

 

Linked List는 노드들이 시퀀스로 연결된 것으로 class로 구현한다.

Linked List의 가장 첫 노드는 head 마지막은 tail로 부른다.

이미지 링크: https://realpython.com/linked-lists-python/

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

 

특정 원소를 참조하는 메소드를 만들어보자.

getAt 메소드는 특정 pos(위치)를 입력 받아 해당 위치의 노드를 반환하는 메소드이다.

getAt 메소드는 O(n) 시간 복잡도를 갖는다.

    # 특정 원소 참조
    def getAt(self, pos):
        # pos가 범위를 벗어나는 경우
        if pos<1 or pos>self.nodeCount:
            return None
        
        i = 1 # index는 1부터 시작
        curr = self.head # 첫 노드부터 탐색
        
        while i < pos:
            curr = curr.next # 다음 노드
            i += 1
            
        return curr

 

리스트 순회 메소드를 만들어보자.

traverse는 head부터 tail까지 노드를 돌아 모든 노드의 데이터를 반환한다.

traverse 메소드는 O(n) 시간 복잡도를 갖는다.

    # 리스트 순회
    def traverse(self):
        results = []
        
        curr = self.head
        
        # 빈 리스트의 경우
        if curr == None:
            return answer
        
        # curr가 None이면 반복문 탈출
        # => curr가 head부터 tail까지 순회
        while curr != None:
            results.append(curr.data)
            curr = curr.next
            
        return results

 

길이를 반환하는 메소드를 만들어보자.

간단히 nodeCount를 반환하면 된다.

    # 길이 반환
    def getLength(self):
        return self.nodeCount

 

Linked List에 원소를 삽입하는 메소드를 만들어보자.

아래와 같이 pos 위치에 newNode를 삽입하려면 pos-1 위치의 prev 노드에 대한 정보가 있어야 한다.

그리고 newNode를 prev 뒤에 삽입하려면 3가지 절차가 필요하다.

1. prev.next가 newNode.next가 되게끔 링크를 조정해야 한다.
2. newNode가 prev.next가 되게끔 조정해야 한다.
3. nodeCount의 개수를 1증가시켜야 한다.

여기서 첫 번째와 두 번째의 순서는 바뀌면 안 된다. 만약 두 번째를 먼저 하게 되면 원래의 prev.next(pos+1 위치)가 newNode로 바껴버려 첫 번째를 수행할 수 없게 되버린다.

이러한 조건 말고도 고려해야 할 것이 있다.

바로 맨 앞에 삽입하는 경우와 맨 뒤에 삽입하는 경우 그리고 빈 리스트에 삽입하는 경우를 생각해야 한다.

• 맨 앞에 삽입하는 경우는 pos가 1일 때이고 prev가 없으며 head를 조정해야 한다.
• 맨 뒤에 삽입하는 경우는 pos가 nodeCount+1일 때이고 prev는 앞에서부터 하나씩 찾지 않고 바로 tail으로 지정할 수 있다. 이후 tail을 조정해야 한다. 
• 빈 리스트에 삽입하는 경우는 위 조건들로 해결된다.

맨 앞 or 맨 뒤에 삽입하는 경우 시간 복잡도는 O(1)이고 중간에 삽입하는 경우 시간 복잡도가 O(n)이다.

    # 원소 삽입
    def insertAt(self, pos, newNode):
        # pos가 범위 벗어나는 경우
        if pos<1 or pos>self.nodeCount + 1:
            return False
        
        # 맨 앞에 삽입하는 경우
        if pos == 1: 
            newNode.next = self.head # head 조정
            self.head = newNode
            
        else:
            # 가장 마지막에 삽입하는 경우
            if pos == self.nodeCount+1:
                prev = self.tail # prev는 tail이 됨
            
            # 중간에 삽입하는 경우
            else:
                prev = self.getAt(pos-1)
                
            newNode.next = prev.next
            prev.next = newNode
        
        # 마지막에 삽입되는 경우 tail 조정
        if pos == self.nodeCount+1:
            self.tail = newNode
        
        self.nodeCount += 1
        return True

 

Linked List로부터 노드를 삭제하고 그 값을 반환하는 메소드를 만들어보자.

pos 위치의 curr 노드를 삭제하려면 prev 노드의 정보가 필요하다.

prev가 curr를 가리키는 것이 아닌 curr의 다음 노드를 가리키도록 해야 한다.

즉, prev.next <- curr.next 가 되어야 한다. 그리고 이 때 nodeCount 또한 1 감소해야 한다.

대략 코드를 작성하면 아래와 같다.

prev = self.getAt(pos-1) # prev를 얻는다.
curr = prev.next # curr는 prev의 next
prev.next = curr.next # prev의 next에 curr의 next가 오게끔 한다.
self.nodeCount -= 1 # 노드 개수 1 감소
return curr.data # 삭제하려는 curr의 데이터 반환

삭제 또한 고려해야 할 점들이 있다.

• 맨 앞의 노드를 삭제하는 경우 head를 조정해야 한다.
• 맨 뒤의 노드를 삭제하는 경우 tail을 조정해야 하고 prev의 next가 None이 되도록 해야 한다.
• 유일한 노드를 삭제하는 경우 prev를 고려할 필요가 없고 head와 tail을 조정해야 한다.

맨 앞에 삽입하는 경우 시간 복잡도는 O(1)이고 중간 or 맨 뒤에 삽입하는 경우 시간 복잡도가 O(n)이다.

    def popAt(self, pos):
        # pos가 범위를 벗어나는 경우
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        
        # 유일한 노드를 삭제하는 경우
        if self.nodeCount == 1:
            curr = self.head
            self.head = None
            self.tail = None
            
        # 노드가 2개 이상인 경우
        else:
            # 맨 앞의 노드를 삭제하는 경우
            if pos == 1:
                curr = self.head
                self.head = curr.next # head를 조정
            
            else:
                prev = self.getAt(pos-1)
                # 맨 뒤의 노드를 삭제하는 경우
                if pos == self.nodeCount:
                    curr = self.tail
                    self.tail = prev
                    prev.next = None
                # 중간 노드를 삭제하는 경우
                else:
                    curr = prev.next
                    prev.next = curr.next

        self.nodeCount -= 1

        return curr.data

 

마지막으로 두 연결 리스트를 연결하는 메소드를 만들어보자.

이 때 연결할 L 리스트가 비어있는 경우는 L.tail이 None값이 되므로 그 조건을 체크해야 한다.

    # 두 리스트 연결
    def concat(self, L):
        self.tail.next = L.head
        
        # L 리스트가 비어있는 경우
        if L.tail:
            self.tail = L.tail
        
        self.nodeCount += L.nodeCount

 

전체 코드는 다음과 같다.

class LinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = None
        self.tail = None
    
    # 특정 원소 참조
    def getAt(self, pos):
        # pos가 범위를 벗어나는 경우
        if pos<1 or pos>self.nodeCount:
            return None
        
        i = 1 # index는 1부터 시작
        curr = self.head # 첫 노드부터 탐색
        
        while i < pos:
            curr = curr.next # 다음 노드
            i += 1
            
        return curr
    
    # 리스트 순회
    def traverse(self):
        results = []
        
        curr = self.head
        
        # 빈 리스트의 경우
        if curr == None:
            return answer
        
        # curr가 None이면 반복문 탈출
        # => curr가 head부터 tail까지 순회
        while curr != None:
            results.append(curr.data)
            curr = curr.next
            
        return results
    
    # 길이 반환
    def getLength(self):
        return self.nodeCount
    
    # 원소 삽입
    def insertAt(self, pos, newNode):
        # pos가 범위 벗어나는 경우
        if pos<1 or pos>self.nodeCount + 1:
            return False
        
        # 맨 앞에 삽입하는 경우
        if pos == 1: 
            newNode.next = self.head # head 조정
            self.head = newNode
            
        else:
            # 가장 마지막에 삽입하는 경우
            if pos == self.nodeCount+1:
                prev = self.tail # prev는 tail이 됨
            
            # 중간에 삽입하는 경우
            else:
                prev = self.getAt(pos-1)
                
            newNode.next = prev.next
            prev.next = newNode
        
        # 마지막에 삽입되는 경우 tail 조정
        if pos == self.nodeCount+1:
            self.tail = newNode
        
        self.nodeCount += 1
        return True
    
    def popAt(self, pos):
        # pos가 범위를 벗어나는 경우
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        
        # 유일한 노드를 삭제하는 경우
        if self.nodeCount == 1:
            curr = self.head
            self.head = None
            self.tail = None
            
        # 노드가 2개 이상인 경우
        else:
            # 맨 앞의 노드를 삭제하는 경우
            if pos == 1:
                curr = self.head
                self.head = curr.next # head를 조정
            
            else:
                prev = self.getAt(pos-1)
                # 맨 뒤의 노드를 삭제하는 경우
                if pos == self.nodeCount:
                    curr = self.tail
                    self.tail = prev
                    prev.next = None
                # 중간 노드를 삭제하는 경우
                else:
                    curr = prev.next
                    prev.next = curr.next

        self.nodeCount -= 1

        return curr.data
    
    # 두 리스트 연결
    def concat(self, L):
        self.tail.next = L.head
        
        # L 리스트가 비어있는 경우
        if L.tail:
            self.tail = L.tail
        
        self.nodeCount += L.nodeCount

 

참고

프로그래머스 [어서와! 자료구조와 알고리즘은 처음이지?] 강의를 공부하고 작성한 글입니다.