[Algorithm] 연결 리스트

* Python을 기준으로 합니다

---

연결 리스트 (Linked List)

- 개념

• 연결 리스트 : 각 데이터들이 순서대로 링크를 통해 연결된 구조
  
  • 연결 리스트에서 하나의 노드(Node)는 데이터와 링크(Link)를 가짐
  • 링크는 다른 노드의 주소를 가리키는 역할
• 연결 리스트의 주요 연산
  
  • `insert()` : 특정 위치에 새로운 데이터를 삽입
  • `delete()` : 특정 위치의 데이터를 삭제
  • `isEmpty()` : 리스트가 비어있으면 `True` 아니면 `False`
  • `size()` : 리스트의 크기 (들어있는 데이터 수) 반환
• 배열과 연결 리스트의 비교
  1. 리스트 요소 접근
     • 배열은 모든 데이터가 크기가 같고 연속적인 메모리 공간에 위치함
       - $k$번째 데이터의 위치는 데이터 크기와 $k$를 곱한 다음, 시작 주소에 더해주면 됨
     • 연결 리스트는 $k$번째 노드까지 순서대로 링크를 따라 이동해야 함
       - 데이터 조회 측면에서는 배열이 효율적임
  2. 리스트의 삽입
     • 배열은 중간에 자료를 삽입하려면 해당 위치 이후의 모든 데이터를 뒤로 shift 해야 함
     • 연결 리스트에서는 삽입할 위치 이전/이후의 링크만 수정하면 됨 (그 외의 다른 노드는 영향을 받지 않음)
       - 데이터 삽입 측면에서는 연결 리스트가 효율적임
  3. 리스트의 삭제
     • 삽입과 마찬가지로 중간의 데이터를 삭제하면 해당 위치 이후의 모든 데이터를 앞으로 shift 해야 함
     • 연결 리스트는 삭제할 위치 이전/이후의 링크만 수정하면 됨
       - 데이터 삭제 측면에서도 연결 리스트가 효율적임
  4. Python에서
     • Python의 리스트는 '리스트 자료구조'를 '배열 형태로써 구현'한 것
     • 따라서 Python의 리스트는 배열과 마찬가지로 데이터 조회는 효율적이지만, 삭제/삽입은 비효율적임
• 연결 리스트의 종류
  • 단순 연결 리스트 (Singly Linked List) : 한 방향으로만 연결된 리스트
  • 이중 연결 리스트 (Doubly Linked List) : 하나의 노드가 이전/이후 노드의 링크를 모두 가지는 리스트
  • 원형 연결 리스트 (Circular Linked List) : Tail 노드의 링크가 `None`이 아니라 Head의 주소를 가리키는 리스트

연결 리스트의 구조

- 구현

1. 단순 연결 리스트의 구현

• Node class 정의

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

• 단순 연결 리스트 class 정의
  - `append()`, `insert()`, `delete()`, `isEmpty()` 연산 정의

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data): #연결 리스트 맨 마지막에 추가
        if self.head is None:
            self.head = Node(data)
        else:
            node = self.head
            while node.link is not None:
                node = node.link
            node.link = Node(data)

    def search(self, pos):
        node = self.head
        i = 0
        
        while i < pos:
            node = node.link
            i += 1
        return node

    def insert(self, pos, data): #특정 pos에 node 삽입
        if pos == 0:
            new_node = Node(data)

            tmp = self.head
            self.head = new_node
            self.head.link = tmp
        elif pos == self.size:
            node = self.search(pos-1)

            new_node = Node(data)
            node.link = new_node
        else:
            node = self.search(pos)

            new_node = Node(data)
            tmp = node.link
            node.link = new_node
            new_node.link = tmp

    def delete(self, pos): #특정 pos의 node 삭제
        if pos == 0:
            tmp = self.head
            self.head = tmp.link
            del tmp
        else:
            prev = self.search(pos-1)
            tmp = prev.link
            prev.link = prev.link.link
            del tmp

    def print(self):
      node = self.head

      while node is not None:
        print(node.data, end=' -> ')
        node = node.link
      print('None')
    
    def isEmpty(self): #연결 리스트가 비어있는지 확인
      return self.head==None

2. 단순 연결 리스트의 출력

s = LinkedList()
print(s.isEmpty()) #True

s.append(5)
s.print() #5 -> None

print(s.isEmpty()) #False

s.append(6)
s.append(4)
s.print() # 5 -> 6 -> 4 -> None

s.insert(0, 10)
s.insert(1, 43)
s.print() #10  -> 5  -> 43  -> 6  -> 4 -> None

s.delete(1)
s.print() #10  -> 43  -> 6  -> 4 -> None