[자료구조] #4_1 링크드 리스트

** 링크드 리스트(Linked List)

- 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조

   cf) 배열: 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조 / 예약 필요

- 본래 C언어에서 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원

 

 

 

** 링크드 리스트의 구성 요소 및 구조

- 노드(Node): 데이터 저장 단위로 (데이터 값, 포인터)로 구성

- 포인터(Pointer): 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

- 일반적인 링크드 리스트의 형태

 

클릭시 출처로 이동

 

 

 

** 링크드 리스트 간단한 구현

---

# 노드 구현

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

 

# 데이터 연결을 위한 함수 구현

def add(data):
    node = head
    while node.next: # 다음 주소가 None이 아닐 때까지
        node = node.next
    node.next = Node(data)

 

node1 = Node(1)
head = node1
for index in range(2, 10):
    add(index)

 

# 데이터 출력

node = head
while node.next:
    print(node.data)
    node = node.next
print (node.data)

---

 

 

** 링크드 리스트 장단점

- 장점: 미리 데이터 공간을 할당하지 않아도 됨 <-> 배열

- 단점

  1) 연결을 위한 별도의 공간이 필요하므로, 저장공간 효율이 높지 않음

  2) 연결 정보를 찾는 시간이 필요하므로, 접근 속도가 느림

  3) 중간 데이터 삭제 및 삽입시, 앞뒤 데이터의 연결을 재구성해야 하는 작업 필요