자료구조 - 선형자료구조 - 단순연결리스트

1. 단순 연결 리스트

연결 리스트의 종류

연결리스트의 종류로는 3가지가 있으나 원형 연결리스트와 이중 연결리스트는 제외하고

단순 연결 리스트만 다루어보자

 

연결리스트는 배열과 비슷해보이나 배열과는 다르게 중간에 데이터를 넣고 지우기가 굉장히 간편하다.

배열의 경우, 새로운 값을 넣거나 없앨 때, 인덱스 값이 다 조정이 되지만 연결리스트는 그저 두 데이터 사이에 값을 넣으므로 대상이 되는 두 자료만 바꾸어주면 되기 때문이다.

 

1-1. 구현

구현을 해보자 우선 클래스부터 만들어보자

class Node:
    def __init__(self) -> None:
        self.data = None # 현재 값
        self.link = None # 다음 노드 포인터

    def __str__(self) -> str:
        return f'{self.data}'

Node라는 클래스를 사용해서 연결 리스트의 기본을 만들었다.

node1 = Node()
node1.data = '다현'

print(node1)

node1을 만들고 새로운 값을 넣는다.

이러한 과정을 여러번 한다.

node2 = Node()
node2.data = '정연'
node1.link = node2
node3 = Node()
node3.data = '쯔위'
node2.link = node3
node4 = Node()
node4.data = '사나'
node3.link = node4
node5 = Node()
node5.data = '지효'
node4.link = node5

데이터를 넣어준 모습

print(node1.data, end = ' -> ')
print(node1.link.data, end = ' -> ')
print(node1.link.link.data, end = ' -> ')
print(node1.link.link.link.data, end = ' -> ')
print(node1.link.link.link.link.data)

# 실행 결과
# 다현 -> 정연 -> 쯔위 -> 사나 -> 지효

넣어준 데이터를 출력해보자

print문이 많이 사용되었지만 입력받는 데이터가 정상적으로 나오는 것을 볼 수 있다.

 

newNode = Node()
newNode.data = '재남'
newNode.link = node2.link # node3
node2.link = newNode

새로운 데이터를 넣어보자, 2번 노드('재남')에 새로운 노드를 삽입했다.

 

del(node3)

이번엔 3번노드('쯔위')를 삭제해 보았다.

 

print(node1.data, end = ' -> ')
print(node1.link.data, end = ' -> ')
print(node1.link.link.data, end = ' -> ')
print(node1.link.link.link.data, end = ' -> ')
print(node1.link.link.link.link.data)

# 실행결과
# 다현 -> 정연 -> 쯔위 -> 사나 -> 지효

이렇게 편집된 자료를 출력한 모습이다.

재남이 중간에 추가되고 쯔위가 삭제된 모습을 볼 수 있다.