[9일차 과제] 자료구조(연결 리스트, 이중 연결 리스트)

1. 링크드 리스트(Linked List)란 무엇인지 조사하기
2. 링크드 리스트의 구조(Node, Data, Next Pointer) 설명하기
3. 링크드 리스트의 동작 원리 정리하기
   • 데이터 추가(삽입)
   • 데이터 삭제
   • 데이터 탐색
4. 배열(Array)과 링크드 리스트의 차이점 비교하기
5. 링크드 리스트의 장점과 단점 정리하기
6. 링크드 리스트가 실제로 사용되는 사례 조사하기
7. 파이썬으로 단일 링크드 리스트(Singly Linked List)를 직접 구현해보기
   • Node 클래스 구현
   • LinkedList 클래스 구현
   • 삽입, 삭제, 조회 기능 구현
8. 추가 : 더블 링크드 리스트(Doubly Linked List) 에 대해서도 조사

---

# 연결 리스트 (Singly Linked List)

1. 설명 및 장단점

• 흩어져 있는 데이터를 화살표로 연결해서 관리하는 데이터 선형 자료 구조
  ex. 음악 재생 목록(다음으로 넘어가기). 웹 브라우저 방문 기록. LRU Cache. 
• 데이터의 삽입, 삭제에 따라 연결 리스트의 크기가 증가하거나 감소 가능 (= 크기가 동적)
• 맨 앞의 노드를  head라고 하고 head는 첫 번째 노드를 가리키는 링크만 존재
• 구조
  • Node : 연결 리스트의 기본 단위. 데이터 필드와 다음 노드를 가리키는 링크 필드로 구성
  • Data : 저장하고자 하는 실제 값
  • Next Pointer(Link) : 각 노드가 다음 노드의 주소값
• 동작원리
  • 데이터 삽입 :중간에 데이터를 추가하는 경우, 이전 노드의 링크를 새 노드에 연결하고, 새 노드의 링크를 다음 노드에 연결
  • 데이터 삭제 : 삭제하려는 노드의 이전 노드의 링크를 삭제하려는 노드의 다음 노드에 연결
  • 데이터 탐색 : 첫 번째 노드인 헤드(Head)부터 순차적으로 링크를 타고 탐색 (순차 접근). 특정 인덱스에 바로 접근이 불가능.
• 시간 복잡도 : 

	단순 연결 리스트	이중 연결 리스트	순환 연결 리스트
조회	O(n)	O(n)	O(n)
삽입, 삭제	O(1)	O(1)	O(1)
리스트 전체 순회	O(n)	O(n)	O(n)

• 장점
  • 크기 조절 가능
  • 삽입, 삭제 연산에 유리 (앞 뒤 데이터의 위치 이동 필요 없이 참조만 변경)
• 단점
  • 탐색 시간이 오래 걸림 (특정 위치에 있는 요소에 연결된 링크를 타고 접근하기 때문)
  • 추가 메모리 공간 (Next Pointer도 저장해야하므로 추가적 메모리 소비 발생)

2. 단일 연결 리스트 구현

# Node 구현
class Node: 
    def __init__(self, data):
        self.data = data        # 데이터 필드
        self.next = None        # 참조

# SinglyLinkedList 구현
class SinglyLinkedList:
    def __init__(self):
        self.head = None                        # 리스트 시작 참조

    # 데이터 삽입 (맨 앞 또는 맨 뒤에 삽입)
    def append(self, data):
        new_node = Node(data)                   # 새로운 노드 생성 (아직 리스트에 연결되지 않은 상태)

        # 리스트가 비어있는 경우 (= head가 None인 경우)
        if self.head is None:       
            self.head = new_node                # 새 노드를 첫 번째 노드로 연결
            return
        
        # 리스트가 비어있지 않은 경우
        current = self.head                     # 현재 위치를 head로 설정하고
        while current.next is not None:         # 마지막 노드로 이동 후
            current = current.next 
        current.next = new_node                 # 새 노드를 마지막에 연결

    # 데이터 삽입 (중간에 삽입)
    def insert(self, data, position):
        if position == 0:                       # 삽입하려는 위치가 0(맨 앞)인 경우
            new_node = Node(data)               # 새로운 노드 생성 (아직 리스트에 연결되지 않은 상태)
            new_node.next = self.head           # 기존 리스트를 먼저 연결 
            self.head = new_node                # head를 새 노드로 변경
            # 위 두 코드의 순서가 바뀌면 새로 들어온 노드가 자기 자신을 가리키는 구조가 되어버리고 기존 리스트를 잃게 됨
            return                              
    
        # 원하는 위치 바로 앞 노드로 이동
        current = self.head                 # 현재 위치를 맨 앞(head)으로 초기화한 후
        for _ in range(position - 1):       # 삽입 위치(position)의 바로 이전 노드(position - 1)로 이동
            if current is None:
                raise IndexError("Invalid Index")
            current = current.next

        # 원하는 위치로 이동했으니까 데이터 삽입
        new_node = Node(data)               # 새로운 노드 생성 (아직 리스트에 연결되지 않은 상태)
        new_node.next = current.next        # 새 노드가 원래 current 다음에 있던 노드를 가리키도록 연결
        current.next = new_node             # 이전 노드(current)가 새 노드를 가리키도록 연결

    # 데이터 삭제
    def remove(self, key):
        current = self.head                 # 참조 변수 기본값을 맨 앞(head)로 설정
        prev = None

        # 맨 앞(head) 노드를 삭제
        if current is not None and current.data == key:     # 기본값이 맨 앞이니까 데이터가 None이 아니고(=맨 앞에 데이터가 존재하고 =리스트가 비어있지 않고) 맨 앞 노드(head)와 삭제하려는 값(key)이 같으면
            self.head = current.next        # head를 다음 노드의 데이터와 연결
            current = None                  # 참조를 제거
            return

        # 중간 노드 삭제하기 
        # 삭제하려는 데이터를 찾기 위해 리스트 순회 (prev와 current를 같이 이동)
        while current is not None and current.data != key:  # 노드가 존재하고 삭제할 데이터를 찾을 때까지 리스트 순회
            prev = current                  # 현재 노드를 이전 노드(prev)로 저장
            current = current.next          # 현재 노드를 다음 노드로 이동

        if current is None:                 # 삭제하려는 데이터가 없는 경우 종료
            return
        
        prev.next = current.next            # 이전 노드(prev)가 삭제할 노드의 다음 노드를 가리키도록 연결
        current = None                      # 삭제하려는 노드(current)를 가리키는 참조 제거. 파이썬에서는 이 코드 없어도 데이터가 삭제되긴함
        
    # 데이터 조회
    def display(self):
        elements = []                       # 조회한 결과를 담아 출력할 빈 리스트 생성
        current = self.head                 # 순회 시작을 위해 head를 가리킴
        while current is not None:          # 노드가 존재하는 동안 반복
            elements.append(str(current.data))      # current의 data를 문자열로 형변환 후 elements에 추가
            current = current.next                  # 현재 노드(current)의 다음으로 이동
        elements.append("None")             # 노드가 끝나면 마지막으로 None을 추가함 (연결 리스트의 마지막을 표현)
        print(" -> ".join(elements))        # elements의 요소들을 -> 로 연결

---

# 배열과 연결리스트의 차이

• 배열 : 데이터를 연속된 메모리 공간에 저장
• 연결리스트 : 메모리에 여기저기 흩어진 데이터를 포인터로 연결

	배열	연결 리스트
저장 방식	연속 메모리	비연속 메모리
접근	O(1)	O(n)
삽입	O(n)	O(1) ~ O(n)
삭제	O(n)	O(1) ~ O(n)
메모리 사용	데이터 (효율적)	데이터 + 포인터 (추가 비용)
크기 변경	x	o

---

# 이중 연결 리스트 (Double Linked List)

• 각 노드가 이전 노드와 다음 노드를 모두 기억하는 연결 리스트
• 양방향 탐색(이동) 가능
• 구조
  • Prev : 이전 노드를 가리키는 참조
  • Data : 실제 데이터 값
  • Next : 다음 노드를 가리키는 참조
• 메모리 사용량이 단일 연결 리스트보다 많다
• Prev가 추가되어서 구현하는데에 더 어렵다

---

[과제 후기]

- 웹 브라우저 방문 기록 부분에서 뒤로가기를 스택으로 처리한다고 찾았었는데, 연결 리스트로도 가능하지 않나? 해서 더 자세히 찾아보았다. "뒤로 가기" 기능의 경우, 실제로는 스택 2개를 사용한다. Back Stack과 Forward Stack. 뒤로가기 스택과 앞으로가기 스택. 이중 연결 리스트로도 구현이 가능하다. 뒤로가기만은 스택, 뒤로가기 앞으로가기는 스택 2개, 방문 기록 전체 관리에는 이중 연결 리스트가 적합한 것 같다. 

- 생각보다 일상에서 자료구조를 적용할 수 있는 사례가 많다.

- 배열, 스택, 큐보다 연결리스트의 구현이 조금 더 복잡하고 길어서 정리하는데 오래걸렸다. 그래도 직접 구현해보면서 자료구조에 대해 알아가게 되어서 뿌듯한 시간이었다.

- 정리하면서 포인터라는 단어를 사용한 것 같은데 사실 파이썬에는 없는 개념이라 참조라는 표현이 더 정확하다.