대표적인 데이터 구조 : 링크드 리스트(Linked List)

링크드 리스트 구조

• 연결 리스트라고도 부른다!
• 배열은 순차적으로 연결된 공간에 데이터를 나열하는 것이라면, 링크드 리스트는 떨어진 곳에 존재하는 데이터를 연결해주는 구조를 통해 관리하는 데이터 구조
• 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원!

• 리스트 링크드 기본 구조와 용어
  -노드 : 데이터 저장 단위로 구성
  -포인터 : 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

• 일반적인 형태
  

---

링크드 리스트 간단한 구현

Node 구현

• 보통 파이썬에서는 링크드 리스트 구현 시, 클래스를 이용
• 클래스 잘 모르니까 참고! : https://www.fun-coding.org/PL&OOP1-3.html

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

위의 코드를 아래와 같이 작성할 수 있다.

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

위에와 차이는 내가이제 next를 내비두고 data 인자하나만 넣어도 next에 알아서 None이 들어가준다!

이해가 됐다면 시작해보자!

node1 = Node(1)
node2 = Node(2)
node1.next = node2 # 노드 1 다음 노드2 연결해준 코드

head = node1 # 얘가 우리가만들고자하는 링크드리스트의 첫번째임은 선언해야지
# 링크드리스트로 데이터 추가하기

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

#일단은 더해주는거 따로 만들어보기
def add(data):
    node = head
    while node.next: #노드의 넥스트가 있니?
        node = node.next  # 있으면 위에 노드가 바뀌겠지? 없으면 그게 마지막노드니 와일문 끝인거고
    node.next = Node(data) # 클래스에 다시 data인자를 넣어준거야 

테스트 해보도록 한다.

node1 = Node(1)
head = node1

for i in range(2,10):
    add(i)
    
#출력해봐!
node = head
while node.next:
    print(node.data)
    node = node.next
print(node.data)

---

링크드 리스트의 장단점!

• 장점 :
  -미리 데이터 공간을 할당하지 않아도 됨
• 단점 :
  -연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음
  -연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
  -중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요