[Data Structure]Linked List

💡 연결리스트(Linked List)

📌 연결리스트란?

연결리스트는 다른 추상 자료형(Abstract Data Type)을 구현할 때 기반이 되는 기초 선형 자료구조이다.

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장한다. 연결리스트의 두드러지는 특징들을 배열과 비교해서 보면 좋다.

출처: <파이썬 알고리즘 인터뷰> p.199, 책만, 2020

📚 배열 VS 연결리스트

• 배열은 물리적인 메모리 주소가 연속적이고, 연결리스트는 물리 메모리 주소가 연속적이지 않고 랜덤이다.
• 배열은 삽입/삭제가 O(n)의 시간이 걸리지만, 동적으로 연결된 연결리스트는 삽입/삭제에 O(1)이 걸린다.
• 배열은 각 원소에 인덱스로 O(1)의 시간으로 손쉽게 접근이 가능하다. 그러나 연결리스트는 O(n)의 시간이 소요된다. (배열과 다르게 연결된 메모리가 아니기 때문에, 데이터를 찾기 위해서는 모든 노드를 거쳐서 탐색해야 한다.)

📌 연결리스트 종류

연결리스트에는 싱글 연결리스트(Singly Linked List), 더블 연결리스트(Doubly Linked List), 원형 연결리스트(Circular Linked List)가 있다.그 중 이 글에서는 가장 기본적인 싱글 연결리스트에 대해 다룰 예정이다.

📌 싱글 연결리스트(Singly Linked List)

자료구조에 대한 구현보다는 간단하게 연결 가능한 노드만 정의해서 노드를 가지고 연결리스트의 동작을 살펴 보려한다.

자세한 구현은 파이썬으로 구현한 자료구조 - 연결 리스트 혹은 파이썬 자료구조 8-1장. 연결 리스트 글을 참고하세요.

📚 노드 정의

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

📚 연결리스트 생성

보통 헤더를 선언하여 연결리스트를 생성하고,헤더를 통해 다른 모든 노드를 탐색하고 참조할 수 있다.따라서, head를 직접 이동시키지 않고, node=head로 head주소를 참조하여 사용한다.(원래 헤더는 data를 포함하고 있지 않으며, 헤더의 다음 노드부터 데이터를 가지나 편의상 임의의 값을 넣고 다음 노드부터 사용해도 되고, head노드 부터 사용해도 된다.)

head = ListNode(0)

📚 노드 추가(삽입)

#add new_node
curr_node = head

new_node = ListNode(1)
curr_node.next = new_node
curr_node=curr_node.next

curr_node.next = ListNode(2)
curr_node=curr_node.next

curr_node.next = ListNode(3)
curr_node=curr_node.next

curr_node.next = ListNode(4)
curr_node=curr_node.next

📚 전체 연결리스트 출력 (탐색)

#print all node
node=head
while node:
    print(node.val)
    node=node.next
''' 출력결과 : 0,1,2,3,4 '''

📚 노드 탐색하여 삭제

#delete node by value
node=head
while node.next:
    if node.next.val==2:
        next_node=node.next.next
        node.next=next_node
        break
    node=node.next

node=head
while node:
    print(node.val)
    node=node.next
''' 출력결과 : 0,1,3,4 '''