Linked List

참고/그림 출처 : https://realpython.com/linked-lists-python/

Array의 단점
→ memory address에 크기를 미리 지정한 후 read, insert, delete, searching을 해야하는 번거로움 존재합니다.

Array의 단점을 개선하기 위해 나온 것이 “linked list” 입니다.

Linked List의 구조

1) Node

• 데이터와 다음 데이터를 가리키는 주소를 뜻합니다.
  
  

2) Pointer

• 각 노드에서 다음 데이터를 가리키는 주소값을 가집니다.
• 예시에서 3,1,4,10이 데이터의 주소값이 되는 겁니다.

3) Head

• 시작점입니다.
• 예시에서 Head 존에 있는 것이 Head입니다. 1이 Head가 되겠죠?

4) Tail

• 끝점입니다.
• 예시에서 None에 있는 것이 Tail이 됩니다.

5) Next = None / Null

• 데이터가 없는 경우 포인터의 주소값은 (None / Null)로 표시됩니다.
• 예시에서 주소값이 아무것도 없는 노드가 None인 것입니다.

C언어에서의 장단점

장점

1. 미리 데이터를 할당할 필요 없이 유동적으로 데이터 Insert, Delete 가능합니다.
2. 항상 일정한 속도이기에 데이터를 수정할 때 시간복잡도 O(1)을 가집니다.

단점

1. 다음에 오는 데이터를 연결하기 위해선 별도의 주소값을 가져야 합니다.

2. 정보를 찾기 위해 주소를 확인하고, 다음 데이터를 탐색하는 시간이 있기 때문에 접근 속도가 느립니다.

   → 책에서 페이지를 넘기며 정보를 찾듯 저장 장치에서 순차적으로 데이터를 읽어야 하기 때문입니다.

3. 중간에 위치한 데이터 삭제 시, 앞/뒤로 연결된 데이터의 연결을 재구성해야하는 번거로움이 있습니다.

Linked List 생성 예시

파이썬의 리스트가 linked list의 기능 지원해주는데요, 예시를 보겠습니다.

class Node:
    # data만 입력시, data의 초기값은 None, next 초기값은 None
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

# 3개의 node에 대해 linked list 만들기
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node1.next = node2
node2.next = node3

# 네 번째 노드 만들어주기
new_node = Node(4)

# tail node 만드는 방법
current_node = node1
while current_node.next is not None:
    current_node = current_node.next

current_node.next = new_node

# Now the linked list contains nodes with data 1, 2, 3, and 4, linked together.
print(new_node.data)

>> 4

이번 포스팅은 다소 어려운 개념이 맞습니다.
그러니 이 글만 보시고 CS 나만 어렵게 느끼는 건가?라는 생각으로 자책하지 않으셨으면 좋겠습니다.

그럼 안뇽