[자료구조] Python으로 구현하는 자료구조 (1) Linked_list

Programmers Dev Course Week1에서 기본적인 자료구조 관련 내용에 대해 학습중이다.
그 중 이번에 처음 접해본(!) Linked list에 대해 내용을 정리하고자 한다.

출처/프로그래머스 어서와! 자료구조와 알고리즘은 처음이지?

 

Linked_list란?

Linked list는 그냥 List와는 다르게 각 원소들이 연결되어 있는 형태를 가진다.
여기서는 원소 대신 Node라는 표현을 사용한다.

Node는 기본적으로
- 자기 자신이 가지고 있는 Data
- 그 다음 노드가 무엇인지 밝혀주는 Link의 형태로 구성된다.

이는 클래스의 형태로 구현될 수 있다.

class Node:

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

이제 이를 연결시키려고 한다. 연결을 위해서는 시작과 끝 점을 밝혀야 할 것이다. 따라서 초기화 과정에서 head 와 tail을 활용하게 된다. 또한 노드의 길이를 기록하는 nodeCount 변수 또한 추가한다. 여기까지의 과정을 코드로 적어보면 다음과 같다.

class LinkedList:

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

또한 마지막임을 밝히기 위해 마지막 노드는 None을 가리키게 할 것이다.
지금까지의 과정을 그림으로 그리면 다음과 같다.

 

Linked List의 기능 구현

이제 여기에 여러 연산들을 추가할 것이다. 여기서는 다음 4가지를 확인해보자.

(1) 특정 위치에 있는 원소 추출
(2) 연결 리스트 원소 전체 추출하기
(3) 특정 위치에 원소를 삽입하기(정확히는 그 뒤에 바로)
(4) 특정 위치의 원소 제거하기

그 전에, 하나 약속할 점은 일단은, 연결 리스트의 index의 시작은 1로 하자. 0이 아니다.

 

특정 위치에 있는 원소 추출하기

이 메서드의 경우에는, 우선적으로 위치가 유효한지 확인 후, pos까지 가서 원소를  꺼내오면 될 것이다.

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.data

한 가지 우려되는 점은, 보통 연결 리스트의 끝까지 가서 변화가 일어날 점이 많은데 기본적으로 탐색 자체를 처음부터 계속 끝까지 돌려줘야 한다는 것이다. 이에 대한 해결방안이 있는데, 이는 일단은 다음에 알아보도록 하자.

 

연결리스트 원소 전체 추출하기

이것의 경우는 그저 head 부터 tail까지 전체 순회하여 리스트에 append시키면 충분할 것이다.

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

 

특정 위치 뒤에 바로 원소 삽입하기

이것의 경우는 우선 단순하게 생각하면, 다음 그림처럼 하고 싶을 것이다.

간단하게 생각하면, 삽입하기 직전의 위치까지 와서(prev) 새 노드를 먼저 연결 후, 직전 노드의 연결을 옮겨주는 방식이다. 하지만 여기에는 몇 가지 문제가 존재한다.

(1) 맨 처음 삽입 한다면 어떻게 해야 할까?

(2) 맨 뒤에 삽입할때는 어떻게 해야 할까?

이런 앞, 뒤의 문제가 발생한다. 앞의 경우는 head를 옮겨주면 될 것이고 뒤의 경우에는 새 노드를 tail로 지정해야만 할 것이다. 또한 pos의 위치 설정 오류도 고려하지 않을 수 없다.

이를 반영한 코드는 다음과 같다.

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: # tail 지정을 잊지말자
            self.tail = newNode

        self.nodeCount += 1
        return True

 

특정 위치의 원소 삭제

삭제 또한 쉽게 생각하면 그림과 같을 것만 같다.

먼저 삭제할 앞의 위치를 찾은 후, (연결해줘야 하니까) 삭제할 노트를 찾아 데이터를 꺼낼 준비를 한다.
삭제할 앞의 노드를 삭제할 다음 노드에 연결 후, 삭제할 노드에서 데이터를 꺼내서 보여준다.

하지만 이 역시 다음의 문제들이 있다.

(1) Head를 삭제하는 경우

(2) Tail을 삭제하는 경우

(3) 최초 길이가 1일때는 어떻게 해야 할까?

위의 해결책을 반영한 코드는 다음과 같다.

def popAt(self, pos):
    # 예외처리, 길이가 없어서 언더플로우, 혹은 위치의 오류의 경우
    if self.nodeCount == 0 or pos > self.nodeCount or pos < 1:
        raise IndexError
    # 길이가 1일 경우에는 지우면 비어야 하니까.    
    if self.nodeCount == 1:
        r = self.head.data
        self.head = None
        self.tail = None
            
    else:
        # 마지막거를 지우는 경우는 prev가 None을 가리키게
        if pos == self.nodeCount:
            prev = self.getAt(pos - 1)
            r = prev.next.data
            prev.next = None
            self.tail = prev
        # 처음을 지우는 경우는 헤드가 다음을 가리키게    
        elif pos == 1:
            r = self.head.data
            self.head = self.head.next              
        # 그 외의 일반적인 경우    
        else: 
            prev = self.getAt(pos - 1)
            r = prev.next.data
            prev.next = prev.next.next
                
    self.nodeCount -= 1
    return r   

 

Linked List의 개선 - Dummy Node

헤드를 매번 떼기도 귀찮고 이를 고려하기도 번거롭다. 따라서 우리는 여기서 새로운 아이디어를 생각하게 된다.

바로, "Dummy Node"이다. 그림을 통해 확인해보자.

바로 헤드 노드를 더미로 만드는 것이다. 즉, 맨 앞에 빈 노드 1개가 항상 고정으로 있는 그림이다. 따라서, 노드가 아무것도 없는 상태여도 더미노드가 존재하는 상황이 될 것이다. 더미 노드를 추가함에 따라, 앞에 무언가를 삽입하는 과정에서 헤드를 다시 정의할 이유는 없을 것이다. 대신, 초기 상태의 정의가 바뀐다. 이를 코드로 확인해보자.

def __init__(self): # 시작시 dummy node를 만들고 시작함
	self.nodeCount = 0
	self.head = Node(None)
	self.tail = None
	self.head.next = self.tail

self.head = Node(None)이 더미노드를 만든 것을 의미한다. 이를 통한 삽입과 삭제 연산 또한 간단해진다.|
특히, head를 지정함에 따라 특정 노드 뒤의 삽입/삭제 메서드를 만들수가 있어, insertAt, popAt이 간단해졌다.

def insertAfter(self, prev, newNode): # 특정 노드 뒤의 삽입 연산
	newNode.next = prev.next
	if prev.next is None: # 맨 뒤에 삽입을 할때는 tail 지정
		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):
    curr = prev.next # 지울 대상
    if curr == self.tail: # 만일 꼬리를 지운다면?
        prev.next = None
        self.tail = prev
    else:
        prev.next = curr.next
    self.nodeCount -= 1
    return curr.data

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

 

하지만, 몇 가지 아쉬운 점이 있다.

(1) 노드가 가리키는 방향은 앞으로밖에 갈 수 없다. 뒤로는 못가게 할까?

(2) 삽입. 삭제 연산이 빈번하게 끝에서 일어날거라, 맨 끝을 바로 보게는 못할까.?

이를 해결한 법이 바로 Doubly-Linked list이다.

 

Doubly-Linked List

Doubly - Linked List의 경우에는 이제 좌우로 모두 이동이 가능하게 된다. 따라서 head의 prev에도 None을 배치한다.

각 노드와 Doubly-Linked List의 초기 정의는 다음과 같다.

class Node:

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


class DoublyLinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None) # 더미
        self.tail = Node(None) # 더미
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None

각 더미끼리 서로를 가리키는 모양이 초기의 상태일 것이다.

이제 이에 따라, 연결리스트의 특정 위치의 원소 추출 또한 비교적 성능이 좋아졌다. 오른쪽 절반에 속하는 위치라면 tail부터 거슬러 오게 하면 될 것이다.

def getAt(self, pos):
    if pos < 0 or pos > self.nodeCount: # 위치 오류
        return None

    if pos > self.nodeCount // 2: # 오른쪽 절반이라면 반대로
        i = 0
        curr = self.tail
        while i < self.nodeCount - pos + 1:
            curr = curr.prev
            i += 1
    else: # 왼쪽 절반이면 앞으로
        i = 0
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1

    return curr

 

또한, head와 tail 모두에 dummy가 들어가, head/tail 관련 예외처리 필요 없이, 데이터의 입력/삭제가 구현 가능하다.

물론 하단의 방법과 거의 유사하게 insertBefore, popBefore 또한 구현이 가능할것이다만, 반복적이므로 생략한다.

def insertAfter(self, prev, newNode):
    next = prev.next # 다음 원소를 알아야 링크 재연결이 가능함.
    newNode.prev = prev 
    newNode.next = next
    prev.next = newNode
    next.prev = newNode
    self.nodeCount += 1
    return True

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

    prev = self.getAt(pos - 1)
    return self.insertAfter(prev, newNode)
    
def popAfter(self, prev):
    if prev == self.tail: # tail 다음은 없어서 해야함
        return None
        
    target = prev.next
    
    prev.next = target.next
    target.next.prev = prev
    self.nodeCount -= 1
    return target.data

def popAt(self, pos):
    if self.nodeCount == 0 or pos < 1 or pos > self.nodeCount:
        raise IndexError
            
    if pos == 1: # 길이가 1이면 헤드 다음이 날라간다.
        return self.popAfter(self.head)
        
    else:
        prev = self.getAt(pos -1)
        return self.popAfter(prev)