Algorithm & Data Structure - Linked List(1)

추상적 자료형 / 자료구조

추상적 자료형

추상적 자료형이란 문제를 해결하기 위한 자료의 형태, 연산을 수학적으로 정의한 모델로, 이름 그대로 추상적인 개념일 뿐, 구체적인 구현 방법에 대한 명시는 없다.
대표적인 스택을 예로 들자면 스택의 형태는 삽입한 순서대로 쌓이는 값들의 모임으로 스택의 제일 위에 값을 넣는 push 연산과 스택의 제일 위의 값을 빼서 알려주는 pop 연산이 있다고 할 수 있다.
여기서 스택이 배열로 구현되는지, 연결 리스트(Linked List)로 구현되는지 등의 세부사항은 추상적 자료형에서는 다루지 않는다.

자료구조

자료구조란 추상적 자료형이 정의한 연산들을 구현한 구현체를 말하는 것이다. 스택을 다시 예로 들면, LIFO의 성질을 가진 추상적 자료형이 필요하니 pop, push를 가지는 추상적 자료형을 정의하고, 그것을 구현해서 함수 호출을 관리하는 구현체, 즉 자료구조를 콜 스택이라고 부른다.
따라서 추상적 자료형을 구현한 것이 자료구조라고 생각할 수 있겠다.

Linked List(연결 리스트)

연결 리스트는 추상 자료형인 리스트를 구현한 자료구조로 노드(Node)들을 저장할 때 그 다음 순서의 노드가 있는 위치를 데이터에 포함시켜 저장하는 방식을 사용한다. 1번 데이터에 2번 데이터가 있는 위치를 포함시키고, 2번 데이터에 3번 데이터의 위치를 포함시키는 방식이다.

맨 앞 노드는 head, 맨 마지막 노드를 tail이라고 하여 연결 리스트에게 알려줘 접근이 용이하도록 하고, 노드 전체의 수를 나타내는 값을 연결 리스트에 저장해 리스트 요소의 개수를 확인할 수 있게 한다.

67(head) --> 32 --> 58(tail)
nodeCount = 3

과 같은 형식이다. head는 1번, tail은 nodeCount번이라고 부른다(1번으로 연결 리스트를 시작했을 때의 이점은 후에 설명하겠다).

연결 리스트는 일반적인 배열과 비교해 위와 같은 특징을 가진다.

이제 노드와 연결 리스트를 구현하고 연결 리스트의 연산에 대해 알아보겠다.

우선 노드는

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

과 같이 구현할 수 있다. data는 노드가 가지는 데이터 값이고, next에는 다음 노드(다음 노드의 위치)가 들어간다.

또한 연결 리스트는 위에서 설명한 것과 같이

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

과 같이 구현할 수 있다. 연결 리스트 안의 노드끼리의 연결은 Node 클래스에서 하고 있으니, 연결 리스트의 전체 길이(nodeCount), 연결 리스트의 헤드(head), 연결 리스트의 테일(tail)만 정의해주면 된다.

이제 연결 리스트의 연산에 대해 정의해야 하는데, 연결 리스트는 다음의 연산들을 가진다.

• 특정 원소 참조(Get)
• 리스트 순회(Traverse)
• 전체 길이 얻기(Length)
• 원소 삽입(Insert)
• 원소 삭제(Pop)
• 두 리스트 합치기(Concat)

하나의 연산씩 구현하기 위한 개념에 대해 설명하며 구현해보겠다.

특정 원소 참조

67(1 / head) --> 34(2) --> 58(3 / tail)

과 같은 연결 리스트가 있다고 하면, 2번 인덱스의 노드(의 값)를 얻기 위해서는 배열과 같은 방식(arr[2])을 사용할 수 없다.
연결 리스트는 연속된 위치에 데이터를 저장하지 않고, 무작위의 위치에 노드들이 존재하고 자신의 뒷 노드를 각 노드가 알고 있기 때문에 연결 리스트의 시작 노드(head)에서 원하는 인덱스의 노드에 접근할 때까지 뒤로(next) 가야한다.
코드로 표현하면

class LinkedList:
    def __init__(self):
    	self.nodeCount = 0
        self.head = None
        self.tail = None
    
    def getAt(self, pos):
    	curr = self.head
        i = 1
        while i < pos:
            curr = curr.next
            i+=1
        return curr

과 같다. 그러나 실제로 이 코드를 가지고 여러 테스트 케이스를 돌려보면 에러가 날 수 있는데, 1번 노드(헤드)보다 이전 인덱스의 노드를 찾으려하거나 노드 전체 길이를 넘어가는 인덱스의 노드를 찾으려하면 에러가 난다.
또한 연결 리스트의 테일에 가장 마지막 노드가 저장되어 있는데, 이 방식을 사용하면 가장 마지막 노드를 가져오기 위해 헤드부터 시작해 찾아낸다는 문제가 있다.
에러를 제거하고 테일 속성을 활용하기 위해 코드를 수정하면

class LinkedList:
    def __init__(self):
    	self.nodeCount = 0
        self.head = None
        self.tail = None
    
    def getAt(self, pos):
    	if pos < 1 or pos > self.nodeCount:
            return None
        if pos == self.nodeCount:
            return self.tail
    	curr = self.head
        i = 1
        while i < pos:
            curr = curr.next
            i+=1
        return curr

과 같이 수정할 수 있다.
두개의 조건문을 사용함으로써 잘못된 인덱스에 대해 None을 반환해주고, 원하는 인덱스가 노드 전체 개수와 같으면 연결 리스트의 테일 노드를 반환함으로써 효율을 높였다.

리스트 순회

리스트 순회는 리스트를 처음부터 끝까지 돌면서 모든 값에 접근하는 것으로, 우리는 연결 리스트 안의 노드들의 값을 배열(Array)로 만들어 반환해주는 함수로 만들어보겠다.
리스트 순회는 어찌보면 특정 원소 참조와 비슷하다. 특정 원소 참조는 헤드에서부터 특정 인덱스까지였다면 리스트 순회는 그 특정 인덱스가 연결 리스트의 테일이라고 생각하면 된다.
코드로 구현하면

class LinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = None
        self.tail = None
    
    def getAt(self, pos):
    	if pos < 1 or pos > self.nodeCount:
            return None
        if pos == self.nodeCount:
            return self.tail
    	curr = self.head
        i = 1
        while i < pos:
            curr = curr.next
            i+=1
        return curr
    
    def traverse(self):
    	arr = []
        curr = self.head
        while curr is not None:
            arr.append(curr.data)
            curr = curr.next
        return arr

과 같다.
우선 curr = self.head로 연결 리스트의 헤드를 가져온 후 while문의 조건으로 curr is not None을 줘서 노드가 존재하면 배열에 그 노드의 값을 추가하고 현재 노드의 다음 노드를 가지고 다시 반복문의 조건으로 검증해 반복문을 진행한다.
이런 로직을 사용해 리스트의 헤드에 아무런 값이 없어도(리스트의 길이가 0이라도) 에러 없이 빈 배열이 출력되고, 테일 이후의 노드를 찾으려고해도 노드가 없어 None이 되므로 자동으로 반복문이 종료된다.
어찌보면 특정 원소 참조보다도 간단하게 구현이 가능하다고 할 수 있다.

전체 길이 얻기

이 부분은 로직이라고 할 것도 없이 간단한데 연결 리스트의 속성으로 nodeCount라는 리스트 전체 길이 값을 주었기 떄문에 linked_list라는 연결 리스트가 있다고 한다면

linked_list.nodeCount

와 같이 리스트 전체 길이를 얻을 수 있다.

원소 삽입

드디어 연결 리스트의 강점을 볼 수 있는 원소 삽입이다.
배열(Array)에 원소를 삽입하면 삽입한 위치부터 뒤로 있던 원소들을 뒤로 한칸씩 옮기고 넣고자 하는 원소를 삽입해야 하는데, 연결 리스트에서는 노드들간의 연결 관계만을 바꿔주면 간단하게 원소를 삽입할 수 있다.
아래의 예시를 보자

68(1 / head - next:34) --> 34(2 - next:57) --> 57(3 / tail - next:None)
+ 45 at index 2
=> 68(1 / head - next:45) --> 45(2 - next:34) --> 34(3 - next:57) --> 57(4 / tail - next:None)

원소가 3개인 연결 리스트 중간에 노드를 추가한 모습이다. 노드들에 쓰인 인덱스 번호는 실제로는 기록되지 않는 값으로, 노드들간의 관계만 생각하면 된다.
위의 예시에서 <45 노드>를 삽입하기 위해 간단하게 1번 노드의 next를 <45 노드>로 정하고 <45 노드>의 next를 원래 2번 노드였던 <34 노드>로 정해주면 된다.

출처: Linked List | Set 2 (Inserting a node) - GeeksforGeeks

위 그림을 보면 이해가 잘 될 것이다. E 노드를 삽입하고자 하는 노드라고 생각하면 된다.
위의 방법을 코드로 구현하면

def insertAt(self, pos, newNode):
    prev = self.getAt(pos-1)
    newNode.next = prev.next
    prev.next = newNode

와 같이 할 수 있다. prev는 넣고자 하는 위치 새 노드의 다음 노드로 prev의 다음 노드를 넣어주고 prev의 다음 노드로 새 노드를 지정해 prev노드와 넣고자 하는 위치에 원래 있던 노드 사이에 새 노드를 넣어주었다.
그러나 이렇게만 구현하면 특정 원소 찾기에서 처럼 잘못된 인덱스에 노드를 삽입하고자 할 때 에러가 발생할 수 있고, 헤드나 테일 위치에 노드를 삽입하면 헤드, 테일의 정보가 수정되지 않고 리스트의 전체 길이도 수정되지 않는다는 문제가 있다.
이런 점들을 고치기 위해 다음과 같은 코드를 추가하겠다.

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

우선 제일 위에서 에러를 유발할 수 있는 인덱스 문제를 잡아주겠다.
그러나 노드 삽입시에는 전체 길이보다 +1 된 값까지는 받을 수 있으므로(테일 노드 뒤에 값을 추가하는 경우) 특정 원소 참조의 조건문과 비슷하나 그 부분이 다르다.

그 후 넣고자 하는 위치가 1번 노드이면 넣고자 하는 위치의 이전 노드가 없으므로 넣고자 하는 노드와 현재 헤드 노드의 관계를 연결해주고 헤드를 넣고자 하는 노드로 바꿔주었다.

넣고자 하는 위치가 1번이 아니라면 넣고자 하는 위치 이전의 노드가 필요하므로(<넣고자 하는 위치의 이전 노드 - 넣고자 하는 노드 - 넣고자 하는 위치에 있던 노드> 관계를 만들어주기 위해) getAt을 이용해 가져와주고, 넣고자 하는 위치가 테일의 뒤라면 이전 노드를 self.tail을 통해 가져온다.
그러나 이 부분에서 새로운 노드가 테일이 되어도 리스트의 테일을 수정해주지 않는데, 이는 else문 안에서 테일을 바꿀 경우 새로 추가한 노드가 리스트의 헤드이자 테일일때(빈 리스트에 추가시) 한번 더 테일 값인지 확인해 테일을 수정해줘야 하기 때문이다(if-else를 사용해 삽입할 위치가 헤드인지 아닌지 분류했기 때문).
즉, else문 까지 모두 끝난 다음 새로운 조건문을 생성해(새로 넣은 노드가 테일인지) 리스트의 테일에 새로운 노드를 넣어주었다.

그 후 공통적으로 전체 리스트의 길이가 증가했으므로 모든 조건문 밖에서 리스트의 길이를 1 늘려주고 함수를 종료한다.

출처: Linked List | Set 2 (Inserting a node) - GeeksforGeeks

위의 사진을 참고해서 생각해보면 이해할 수 있을 것이다.

원소 삭제

원소 삭제는 원소 삽입과 매우 유사하다.
삭제하고자 하는 위치 이전의 노드와 삭제하고자 하는 위치 다음의 노드를 연결해주면 연결 리스트 내부에서 삭제하고자 하는 노드를 지울 수 있다.
코드로 구현하면

def popAt(self, pos):
    prev = self.getAt(pos-1)
    data = prev.next.data
    prev.next = prev.next.next

과 같이 할 수 있다.
원소 삽입과 마찬가지로 잘못된 인덱스 처리와 헤드, 테일일 때의 처리, 리스트 전체 길이의 수정을 추가해주면 되는데

def popAt(self, pos):
    if pos < 1 or pos > self.nodeCount:
    	raise IndexError # 잘못된 인덱스 접근 시 에러 발생시킴
    
    if self.nodeCount == 1:
    	data = self.head.data
        self.head = None
        self.tail = None
    
    elif pos == 1:
    	data = self.head.data
        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

과 같이 만들 수 있다.

첫번째 조건문에서는 잘못된 인덱스의 노드를 삭제하려고 하면 에러를 발생시킨다.

두번째 조건문에서는 리스트 전체의 길이가 1이고, 1번 노드를 지우려하면 data에 리스트 헤드의 데이터를 담고 헤드와 테일을 비운다.

세번째 조건문에서는 리스트 전체 길이가 1이 아니고 1번 인덱스를 지우려 하면 data에 리스트 헤드의 데이터를 담고, 리스트 헤드에 헤드 다음 노드를 담아준다.

네번째 조건문에서는 첫번째 노드를 지우려는 것이 아니면 지우려는 노드의 이전 노드가 필요하므로 이전 노드를 가져오고 data엔 이전 노드의 다음 노드(지우려는 노드)의 값을 담아준다. 만약 지우려는 노드가 테일 노드라면 이전 노드를 테일에 담아주고 이전 노드의 다음 노드를 없애주고, 테일 노드가 아니라면 이전 노드를 지우려는 노드의 다음 노드와 연결해준다.

그 후 리스트의 전체 길이에서 1을 빼주고, 뽑아두었던 data를 리턴한다.
원소 삽입과 비슷하게 생각하되 지우려는 값이 헤드, 테일일 때 어떤 로직으로 구현할지 생각해보면 코드를 이해할 수 있을 것이다.

두 리스트 합치기

연결 리스트 두개를 합치는 것은 매우 간단하다.
이미 각 리스트의 헤드, 테일을 알고 있으므로 1번 리스트의 테일 뒤에 2번 리스트의 헤드를 연결하고 1번 리스트의 테일을 2번 리스트의 테일로 하는 방식으로 구현하면 된다.

# L1: 앞 리스트
# L2: 뒤 리스트

L = L1
L.tail.next = L2.head
L.tail = L2.tail

과 같이 구현할 수 있다. 이제 여기서 둘 중 한 리스트가 비어있을 때의 처리만 해주면 된다.
→ 둘 중 한 리스트가 비어있으면 다른 리스트를 리턴하는(둘 다 비어있으면 무엇을 리턴해도 상관이 없음) 방식으로 예외처리를 해줄 수 있다.

정리

지금까지 연결 리스트의 구현과 연결 리스트의 6가지 연산들을 구현해보았다.
물론 여기서 구현한 예외처리, 로직 등은 정답이 아닐 수 있다.
자료구조에 대한 공부는 처음이라 설명도 미흡하고 로직도 조잡한 것 같지만 꾸준히 한다는 생각으로 공부해야겠다.