[algorithm][python] 연결리스트(Linked Lists)

오늘은 연결리스트에 대해 알아보자.

연결 리스트

연결 리스트에서는 원소들이 링크 (link) 라고 부르는 고리로 연결되어 있다.
앞서 살펴본 선형 배열보다 가운데에 있는 원소를 삭제 또는 삽입하는 것을 더 빠른 시간내로 처리하는 것이 가능하다.
이러한 이점 때문에, 원소의 삽입/삭제가 빈번히 일어나는 응용에서는 연결 리스트가 많이 이용된다.
실제 현실에서 스마트 폰 홈버튼을 두 번 누르면 나오는 앱 리스트 같은 경우 이중 연결 리스트 등으로 구현할 수 있을 것이다.

---

파이썬 클래스로 연결리스트 만들어보기

다음과 같이 클래스로 연결리스트를 구현해 볼 수 있다.

노드 구현하기

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

연결 리스트 구현하기

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

---

연결 리스트의 연산들을 구현하기

연결리스트에서 사용되는 연산들을 구현해보자.

특정 위치에 있는 노드를 반환하기

#연결 리스트의 index는 1부터 시작하도록 만들었다. 
def getAt(self, pos):
    if pos <=0 or pos > self.nodeCount:
        return None
    i = 1
    curr = self.head
    while i < pos:
        curr = curr.next
        i += 1
    return curr

연결 리스트에 담겨 있는 item 들을 리스트로 반환하기

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

원소를 삽입하기

• 주의
  삽입하려는 위치가 가장 앞이거나 가장 끝일 때
  head 와 tail 조정 유의

# pos 는 1에서 nodeCount까지의 정수를 의미한다. 
# 삽입에 성공하면 True를, 실패하면 False를 반환한다. 
def insertAt(self, pos, newNode):
    if pos < 1 or pos > self.nodeCOunt + 1:
        return False
    if pos = 1:
        newNode.next = self.head
        self.head = newNode
    else:
        #이전 노드를 찾는다. 
        if pos == self.nodeCount + 1:
            prev = self.tail
        else:
            prev = self.getAt(pos - 1)
        newNode.next = prev.next
        prev.next = newNode

    if pos == self.nodeCount + 1:
        self.tail = newNode
    
    self.nodeCount += 1
    return True

원소를 삭제하기

• 주의
  삭제하려는 node가 맨 앞이거나 맨 끝일 때
  노드가 하나만 있을 때

def popAt(self, pos):
    if pos < 1 or pos > self.nodeCount:
        raise IndexError
    
    if pos == 1:
        data = self.head.data
        if self.nodeCount == 1:
            self.head = None  
            self.tail = None  
        else:
            self.head = self.head.next
            
    else :
        prev = self.getAt(pos-1)
        data = prev.next.data
        if pos == self.nodeCount:
            self.tail = prev
            prev.next = None
        else:
            prev.next = prev.next.next
    
    self.nodeCount -= 1
    return data

연결리스트 두개를 합치기

def concat(self, L):
    self.tail.next = L.head
    if L.tail:
        self.tail = L.tail
    self.nodeCount += L.nodeCount

연산들이 효율적인가?

지금까지 구현한 코드는 getAt이라는 O(n)의 시간 복잡도를 지닌 연산을 이용한다.
때문에 매번 삽입 삭제에서 O(n)의 시간 복잡도를 가질 수 밖에 없다.

앞에 더미 노드를 지니고 있는 연결 리스트

다음 코드로 앞서 구현한 것과는 조금 다른 앞에 더미노드가 추가된 형태의 연결리스트를 구현해보자.
더미 노드를 추가하면 쓰이지 않는 노드가 하나 생기지만 데이터를 담고 있는 모든 노드의 연결 구성이 같아지므로 코드를 좀 더 효율적으로 줄일 수 있게 되는 것을 볼 수 있다.

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

리스트 순회

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

k 번째 원소를 return

#연결 리스트의 index는 0부터 시작할 수 있고 head는 더미노드를 가리킨다. 
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 insertAfter(self, prev, newNode):
    newNode.next = prev.next
    if prev.next is None:
        self.tail = newNode
    prev.next = newNode
    self.nodeCount += 1
    return True

특정 위치에 노드 삽입하기

insertAfter를 이용해서 insertAt 연산을 더 쉽게 만들 수 있다.

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)

원소의 삭제

• 주의
  prev가 마지막 node 일 때 -> None을 리턴하자
  리스트 맨 끝 노드를 삭제할 때 -> tail 조정

def popAfter(self, prev):
        if prev.next == None:
            return None
        data = prev.next.data 
        if prev.next.next == None:
            self.tail = prev    
        prev.next = prev.next.next
        self.nodeCount -= 1
        return data

    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        prev = self.getAt(pos-1)
        return self.popAfter(prev)

두 리스트의 연결

def concat(self, L):
    self.tail.next = L.head.next
    if L.tail:
        self.tail = L.tail
    self.nodeCount += L.nodeCount

연결 리스트의 전체 코드

class Node:

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


class LinkedList:

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


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


    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 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)


    def popAfter(self, prev):
        if prev.next == None:
            return None
        data = prev.next.data 
        if prev.next.next == None:
            self.tail = prev    
        prev.next = prev.next.next
        self.nodeCount -= 1
        return data


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        prev = self.getAt(pos-1)
        return self.popAfter(prev)