[자료구조] 2. 링크드 리스트 - 1 싱글 링크드 리스트

기본적으로 C의 배열은 지정된 크기 이상의 데이터를 넣지 못합니다. 하지만 데이터가 어느 정도로 있을지 정확하게 알 수 없기 때문에 배열의 크기를 바꾸거나 처음부터 크게 잡아야 합니다. 그러면 결국 메모리를 너무 크게 잡게됩니다.

그래서 크기를 유연하게 바꿀 수 있는 구조인 리스트(List)를 만들게 됩니다.

⚠ 기본적으로 파이썬으로 구현하였습니다.(Python 3.10)

 

링크드 리스트

링크드 리스트(Linked List)는 리스트 중 가장 쉽게 구현할 수 있는 기법입니다.

링크드 리스트는 리스트의 요소인 노드(Node)를 연결해서 만드는 방법입니다.

링크드 리스트에서 노드는 데이터를 보관하는 필드와 다음 노드와의 연결 고리인 포인터로 이루어집니다.

이런 노드들을 고리처럼 매달면 링크드 리스트가 되는 것이죠.

여기서 첫번째 노드를 헤드(Head), 마지막 노드를 테일(Tail)이라고 합니다.

새 데이터가 추가될 때마다 노드를 생성해서 테일 뒤에 추가하기만 하면 데이터의 크기를 미리 알 필요가 없습니다.

 

링크드 리스트의 연산

• 노드 생성
• 노드 소멸
• 노드 추가
• 노드 탐색
• 노드 삭제
• 노드 삽입

 

이 정도의 연산을 구현해야 합니다. 이건 이번 글에서 구현할 싱글 링크드 리스트 말고도 더블 링크드 리스트 등에서도 모두 구현해야 하는 것입니다.

 

싱글 링크드 리스트

싱글 링크드 리스트는 말 그대로 포인터가 한쪽 방향으로 연결되어 있다는 뜻입니다.

헤드에서 테일 방향으로만 가는 리스트이죠.

우선 노드의 생성부터 구현을 해보겠습니다.

 

노드 클래스

class SinglyLinkedList:
    # 노드 클래스
    class Node:
        def __init__(self, data, next=None):
            self.data = data
            self.next = next

우선 SinglyLinkedList라는 클래스를 생성해서 사용하도록 하겠습니다.

그 안에 중첩 클래스로 Node라는 클래스를 만들었습니다.

노드 클래스는 data(숫자, 문자열 등이 될 수 있습니다)와 next(포인터)로 구성됩니다.

 

보기 쉽게 포인터 변수 이름을 next로 지었습니다.

이 next에는 다음 노드가 저장되도록 할 것입니다.

 

클래스 생성자

이제 SinglyLinkedList 클래스의 생성자부터 만들어봅시다.

def __init__(self): # 초기 상태 설정(헤드와 크기를 설정해줍니다)
    self.head = None
    self.size = 0

생성자 함수는 SinglyLinkedList의 객체가 처음 생성되었을 때의 설정을 담당한다고 생각하시면 됩니다.

변수 head에는 리스트의 헤드가 저장되고 변수 size는 리스트에 들어있는 노드의 갯수가 저장됩니다.

 

그 다음 필요한 함수 두가지를 추가로 만들어줍시다.

def getSize(self): # 사이즈 변수의 getter
    return self.size
    
def isEmpty(self)->bool: # 리스트가 비어있으면 True, 아니면 False입니다.
    return self.size == 0

먼저 getSize 함수는 사이즈 변수 값을 불러오는 getter 함수입니다.

isEmpty 함수는 리스트가 비었는지 확인하는 함수로, 비어있으면 True를, 비어있지 않으면 False를 반환합니다.

함수 옆에 ->bool은 bool 값으로 반환한다는 의미입니다.

 

노드 생성

이제 본격적으로 노드를 생성하는 함수부터 만들어봅시다.

우선 노드를 생성만 하는 createNode 함수입니다.

def createNode(self, data): # 노드를 생성하는 함수로 말그대로 생성만 하고 리스트에 넣지는 않습니다.
    NewNode = self.Node(data)
    return NewNode

리턴 값이 존재하기 때문에 변수에 저장하면서 호출해야 합니다.

아래처럼 사용하시면 되겠습니다.

NewNode = SLL.createNode(1)

이렇게 하면 노드 클래스의 객체가 생성되어 변수 NewNode에 저장이 됩니다.

 

노드 삭제

이번에는 노드를 삭제해야겠죠?

def deleteNode(self, target): # 노드를 삭제하는 함수입니다.
    del target

이 함수는 앞의 함수와 비슷하게 리스트에서 노드를 없애는 것이 아니라, 메모리에서 노드를 삭제하는 함수입니다.

 

노드 삽입

def appendNode(self, NewNode): # 노드를 추가시키는 함수로 리스트의 맨 마지막 부분에 추가시킵니다.
    if self.isEmpty(): # 리스트가 비어있는 경우
        self.head = NewNode # 맨 앞에 추가
    else:
        current = self.head
        while current.next != None:
            current = current.next
        current.next = NewNode
    self.size += 1

이번엔 appendNode 함수입니다. 이 함수는 리스트의 맨 마지막에 노드를 추가해줍니다.

그래서 헤드 부분부터 시작해 맨 마지막 노드를 찾기 위해 이동합니다.

현재 위치를 가리키는 current 변수에 처음엔 head를 저장하고 current의 포인터가 None 일 때까지 옆으로 이동한 다음

current의 포인터가 None일 때 그 포인터를 새 노드로 바꾸는 작업입니다.

항상 노드를 추가하는 함수에는 size + 1, 삭제하는 함수에는 size - 1을 해주세요

 

이번에는 헤드 부분에 새 노드를 추가해보겠습니다.

함수 insertHead입니다.

def insertHead(self, NewNode): # 헤더부분에 추가합니다.
    if self.isEmpty():
        self.head = NewNode
    else: # 비어있지 않은 경우
        NewNode.next = self.head # 새 노드의 포인터에 원래의 헤더를 추가시키고
        self.head = NewNode #  헤더를 새 노드로 변경해줍니다.
    self.size += 1

헤드 부분에 데이터가 없으면 그냥 넣으면 되겠죠?

만약 데이터가 있다면, 즉 노드가 존재하는 경우에는 새 노드의 포인터에 현재 헤드를 추가시키고 헤드를 새 노드로 변경합니다.

다음 함수는 insertAfter 함수입니다. 이 함수는 특정 위치에 있는 노드 다음에 새 노드를 추가하는 함수입니다.

def insertAfter(self, location, NewNode): # 특정 위치(인덱스) 다음에 새 노드를 추가시키는 함수입니다.
    Current = self.getNodeByLocation(location)
    if Current != None:
        NewNode.next = Current.next
        Current.next = NewNode

이 함수에는 location 변수와 NewNode 변수가 매개변수로 들어갑니다.

location은 인덱스 번호로 이 위치 다음에 새 노드가 추가됩니다. 3을 넣으면 4번에 새 노드가 들어갑니다.

이 함수는 밑에서 설명할 getNodeByLocation 함수를 이용해서 location에 있는 노드를 가져옵니다.

Current 변수에 이 노드를 저장합니다.

이때, Current가 비어있지 않으면 새 노드의 포인터에 현재 노드의 다음 노드를 저장하고 현재 노드의 다음 노드는 새 노드로 변경합니다.

 

 

위 그림을 보시면 3 노드가 4 노드를 포인터로 가리키고 있죠?

여기서 3 노드 뒤에 3500이라는 데이터를 가진 새 노드를 추가해보겠습니다.

그럼 우선 새 노드의 포인터를 4 노드에 연결해야합니다.

 

 

3500 노드의 포인터에 4 노드에 연결이 됐다면 3 노드의 포인터를 3500 노드로 바꿔야겠죠?

 

 

삽입을 해봤으면 반대로 노드를 제거해봐야겠죠?

 

노드 제거

노드를 리스트에서 제거하는 방법은 위에서 본 insertAfter와 유사합니다.

def removeNode(self, target):
    if self.head == target:
        self.head = target.next
        self.deleteNode(target)
    else:
        current = self.head
        while current != None and current.next != target:
            current = current.next
        if current != None:
            current.next = target.next
            self.deleteNode(target)
    self.size -= 1

위의 removeNode 함수는 노드 자체를 넣어서 리스트에서 노드를 제거하는 함수입니다.

그래서 매개변수 target에는 노드가 들어가야합니다.

 

첫번째 if 문을 보면 리스트의 헤드가 target과 같은 경우에는 헤드를 target의 포인터로 바꾸고 target을 삭제합니다.

아닌 경우에는 current 변수에 헤드를 넣고 current의 포인터가 target을 가리킬 때까지 옆으로 이동합니다.

그리고 찾은 노드를 삭제합니다.

 

노드 탐색

이번에는 노드를 탐색해봅시다.

def getNodeByLocation(self, location):
    if location >= self.size:
        print("location Error")
        return None
        
    if location == 0:
        return self.head
    else:
    	current = self.head
        for i in range(0, location):
            current = current.next
        return current

getNodeByLocation 함수는 노드를 인덱스 번호를 이용해서 검색합니다.

매개변수 location에 인덱스 번호를 넣으면 해당 위치의 노드를 반환합니다.

우선 첫번째 if문은 location의 값이 리스트의 크기보다 큰 경우입니다. 이런 경우에는 검색이 불가능하니 Error를 출력합니다.

두번째로 location이 0, 즉 헤드인 경우에는 헤드를 바로 반환합니다.

나머지 경우는 위의 다른 함수들과 같이 맨 앞에서부터 location 위치까지 뒤로가면서 찾습니다.

 

메인

싱글 링크드 리스트 클래스를 모두 구현했습니다.

그럼 이제 마지막으로 사용을 해봐야겠죠?

SLL = SinglyLinkedList() # 객체 생성

# 노드 만들어서 리스트에 추가하기
for i in range(5):
    NewNode = SLL.createNode(i+1)
    SLL.appendNode(NewNode)
size = SLL.getSize() # 리스트 크기 불러오기

# 리스트 요소 출력
for i in range(size):
    print(f'{i}번째 : {SLL.getNodeByLocation(i).data}')

# 헤드에 새 노드 추가
NewNode = SLL.createNode('NewHead')
SLL.insertHead(NewNode)
size = SLL.getSize()

for i in range(size):
    print(f'{i}번째 : {SLL.getNodeByLocation(i).data}')

NewNode = SLL.createNode(3500)
SLL.insertAfter(3, NewNode) # 인덱스 번호 3번 뒤(4번째 뒤가 됨)
size = SLL.getSize()

for i in range(size):
    print(f'{i}번째 : {SLL.getNodeByLocation(i).data}')

# 노드 삭제하기
target = SLL.getNodeByLocation(3)
SLL.removeNode(target)
size = SLL.getSize()

for i in range(size):
    print(f'{i}번째 : {SLL.getNodeByLocation(i).data}')

 

정리

이렇게 싱글 링크드 리스트를 모두 구현해봤습니다.

싱글 링크드 리스트의 장점은 노드를 추가/삽입/삭제하는게 빠르다는 것이고,

반대로 단점은 노드를 탐색하는 것이 느리다는 것입니다.

이 다음으로 해볼 것은 더블 링크드 리스트입니다. 싱글 링크드 리스트와 비교하면서 보시면 좋을 것 같습니다.

 

코드 전체 파일을 첨부해두겠습니다. 필요하시면 다운받아서 사용하셔도 좋습니다.

SLL.py

0.00MB

다음 글에서 뵙겠습니다!