어느덧 한 학기가 다 지나갔습니다. 4학년 1학기 캡스톤 디자인도 순조롭게 마무리 되었고, 종강 하고 보니 어느덧 햇볕이 땀구슬을 맻히게 하는 계절이 왔습니다. 방학 때는 학기 중보다 더 자주 포스팅을 할 수 있습니다!! 오늘은 지난 번(무려 두 달 전…)에 이어서 연결 리스트에 대해 이야기 해보겠습니다. (코드는 복붙이 아니라 교재 보고 제가 입력한 거라 오타가 있을수도 있습니다ㅎㅎ)

  1. 연결 리스트

    연결 리스트의 객체 구조

    연결 리스트는 원소가 추가 될 떄마다 공간을 할당 받아 추가하는 동적 할당 방식 입니다. 이 덕분에 공간 낭비를 피할 수 있습니다. 구체적인 구조는 아래와 같습니다.

    연결 리스트에는 __head와 __numItems라는 개념이 있습니다. __head는 첫 번째 노드에 대한 레퍼런스 입니다. __numItems는 연결 리스트에 들어 있는 원소의 총 수입니다. 기본적으로 헤드가 다음 아이템을 가리키고 있다고 생각하시면 됩니다.

    연결 리스트를 이해하기 위해서는 Node라는 개념도 알아야 합니다. 이 노드가 서로 연결 되어 있다는 점이 단순 배열 리스트와 차이가 있습니다. 대표적인 예시로 앞서 말했던 것처럼 기존 배열 리스트에서 원소를 삽입하는 경우 원소를 한 칸 씩 일일이 움직여야 하는데, 연결 리스트에서는 노드의 연결만 바꿔주면 되기 때문에 더 효율적입니다. 이제 연결 리스트의 객체 구조와 연결 리스트의 작업을 공부해보면 더 잘 와닿으실 겁니다.

    연결 리스트의 작업

    원소 삽입, 삭제, i번 원소 알려주기, x가 몇 번 원소인지 알려주기 등을 중심으로 연결 리스트의 작업에 대해 알아보겠습니다.

    • 원소 삽입

    (1) 원소 삽입

    위 이미지와 같이 연결 리스트에 새로운 원소를 삽입하려고 합니다. 아래 이미지와 같이 노드의 연결만 바꿔주면 삽입을 간편하게 할 수 있습니다.

    원소를 중간이 아닌 마지막 원소 뒤나 첫 번째 원소 앞에 삽입하고자 할 때 과정은 아래와 같습니다.

    (2) 원소 삽입 (마지막 원소)

    (3) 원소 삽입 (첫 번째 원소)

    (1), (2), (3) 과정은 다음과 같이 코드로 구현할 수 있습니다.

     def insert(i,x): # i번째 원소에 x 삽입
     if i == 0: # 첫 번째 원소 삽입
         newNode.item = x # 새 원소 
         newNode.next = __head # newNode의 다음 노드를 현재 첫 번째 노드인 __head로 설정. 즉, 새로운 노드가 기종의 첫 번째 노드를 가리키도록 함
         __head = newNode # 연결 리스트의 첫 번째 노드를 newNode로 갱신. 즉, 새로운 노드를 리스트의 맨 앞에 배치
         __numItems += 1 # 리스트 크기 하나 증가
     else: # 첫 번째가 아닌 i+1번째 원소 삽입
         newNode.item = x # 새 원소
         newNode.next = prev.next # newNode의 다음 노드를 prev노드가 가리키고 있던 노드를 가리키도록 설정
         prev.next = newNode # prev 노드의 다음 노드를 newNode로 설정. 즉, prev 노드가 이제 새로운 노드를 가리키도록 함
         __numItems += 1 # 리스트 크기 하나 증가

    이 과정은 dummy head가 없을 때의 과정입니다. 그렇다면 dummy head를 이용하면 어떻게 바뀔지 알아보겠습니다.

    (4) 원소 삽입 (dummy head 활용)

    더미 헤드는 연결 리스트의 시작 부분에 위치하는 특수한 노드로, 실제 데이터는 포함하지 않지만 리스트의 구조를 단순화하고 다양한 연산을 쉽게 수행하도록 도와줍니다.더미 헤드는 삽입, 삭제 등의 연산을 수행할 때, 특히 첫 번째 노드와 관련된 연산에서 코드의 일관성을 유지하고 예외 처리를 단순화 하는 데 유용합니다. 장점을 요약하면 아래와 같습니다.

    • 리스트의 처음과 끝에 노드를 삽입할 때 특별한 경우를 처리할 필요가 없음.
    • 코드가 간결해지고, 첫 번째 노드와 관련된 연산에서의 복잡성이 줄어듦.

    이번에는 코드부터 먼저 살펴 보겠습니다.

     def insert(i,x): # 더미 헤드 사용하는 경우
     newNode.item = x
     newNode.next = prev.next
     prev.next = newNode
     __numItems += 1

    딱 봤을 때 맨 처음 봤었던 삽입 코드에서 첫 번째(i가 0번째)에 삽입 하는 경우의 예외처리를 없앤 것과 동일합니다. 어떻게 이게 가능할까요?

    위 그림은 더미 헤드를 활용해서 첫 번째 원소에 삽입하는 경우를 나타냅니다.

    더미 헤드가 있기 때문에 첫 번째 원소에 삽입하는 경우에도 prev 노드가 더미 헤드가 될 수 있기 때문에 기존 i번째 삽입과 동일하게 사용할 수 있습니다.

    • 원소 삭제

    (1) 원소 삭제

    (2) 원소 삭제 (마지막 원소)

    원리는 간단합니다. 기존 prev.next를 prev.next.next로 설정하고 원소 크기를 줄이면 연결이 끊긴 원소(삭제 하려는 원소)가 삭제 됩니다.

    마지막 원소를 삭제할 때는 prev.next.next가 none 이라고 생각하면 됩니다.

    (3) 원소 삭제 (첫 번째 원소)

    (1), (2), (3) 과정은 아래 코드와 같이 정의될 수 있습니다.

     if i == 0: # 첫 번째 원소 지울 때
     __head.next = __head.next.next # __head.next를 __head.next.next로 설정
     __numItems -= 1 # 리스트 크기 1 감소
 else:
     prev.next = prev.next.next # prev.next를 prev.next.next로 설정
     __numItems -+ 1 # 리스트 크기 1 감소

    이 경우 역시 더미 헤드가 없는 경우입니다. 더미 헤드가 있는 경우는 어떻게 될 지 예상이 가시나요?? 삽입 과정에서 더미 헤드를 이해하셨다면 삭제 과정에서도 충분히 이해하실 수 있으실 겁니다.

    (4) 원소 삭제 (dummy head 활용)

    더미 헤드를 활용하면 삽입과 마찬가지로 첫 번째 예외처리를 하지 않아도 됩니다. 코드는 아래와 같습니다.

     prev.next = prev.next.next # prev.next를 prev.next.next로 설정
 __numItems -+ 1 # 리스트 크기 1 감소

    삽입과 마찬가지로 더미 헤드를 사용하면 첫 번째 원소에 대한 예외 처리 없이 코드를 구성할 수 있습니다.

    • i번 원소 알려주기 (get(i))

    먼저 i번째 원소를 알려주는 get(i) 함수를 이해하려면 i번 노드를 알려주는 함수 __getNode(i)도 함께 알아야 합니다. 두 코드를 먼저 살펴보겠습니다.

     def get(i):
     if i >= 0 and i <= __numItems - 1: # i가 0 이상이고, 리스트 크기보다 작은지 확인(i의 유효 범위 확인)
         return __getNode(i).item # i가 유효하면 i에 해당하는 노드를 찾고, 노드의 item 값 반환
     else:
         print(i,"가 유효 범위 내에 없습니다.")

 def __getNode(i):
     curr = __head # curr은 현재 노드를 의미함. curr 변수를 더미 헤드로 설정
     for index in range(i+1): # 0부터 i까지 총 i+1번 반복
         curr = curr.next # curr을 현재 노드의 다음 노드로 업데이트
     return curr # 업데이트 되어서 i에 해당하는 노드를 반환

    코드로만 봐도 이해가 되지만 그림과 함께 보면 더 이해가 잘 갈 겁니다. 그럼 그림도 함께 알아보겠습니다.

    예를 들어 i가 3일 때의 원소가 뭐인지 알고 싶으면 get(3)을 사용하면 됩니다.

    찾고자 하는 원소의 인덱스 i가 유효한 범위 내에 있을 때 getNode(i)함수를 호출합니다. getNode(i)에서 초기 curr는 더미 헤드로 설정 됩니다.

    0부터 i까지, 즉, i+1번 반복하여 curr를 업데이트 합니다. 그 curr 값의 item(코드에서는 __getNode(3).item)을 출력하면서 연결 리스트의 i번 원소를 알려주게 됩니다. 예시로 i가 3일 때를 찾고 있으므로 그림에서는 40이 출력 되겠네요!!!

    • x가 몇 번 원소인지 알려주기(index(x))

    이번에는 x를 입력하면 x가 몇 번째 원소인지 알려주는 index(x)함수에 대해 알아보겠습니다. 이번에도 코드를 먼저 본 뒤 그림과 함께 설명 드리겠습니다. 교재에 나오는 코드와 살짝 다를 수 있습니다.

     def index(x):
     curr = __head # curr를 더미 헤드로 설정
     for index in range(__numItems): # 리스트의 크기만큼 반복
         curr = curr.next # curr을 현재 노드의 다음 노드로 업데이트
         if curr.item == x: # 현재 노드의 item값이 x와 같으면 index값 반환
             return index
        
     print("값을 찾지 못했습니다.") # 루프가 끝날 때까지 x값을 찾지 못하면 메시지 출력
     return -12345 # x 값을 못찾았음을 나타내기 위한 -12345값 반환

    예를 들어 리스트에서 35의 값이 몇 번째 원소인지 알고 싶은 경우, 즉, index(35)를 생각해보겠습니다.

    찾고자 하는 x값을 루프 내에서 curr값을 업데이트 하면서 값을 찾습니다.

    35 값을 갖고 있는 curr를 찾으면 index로 반환합니다. 즉 index(35) = 2가 됩니다.

    만약 index(99)를 하면 어떻게 될까요?? 루프 반복 동안 리스트 내에 값이 없으므로 다음과 같이 출력을 하게 될 것입니다.

     값을 찾지 못했습니다.
 -12345
    • 기타 작업들

    아래는 기타 작업들의 함수입니다. 간단하므로 아래 코드로 대체하겠습니다.

     def isEmpty(): # 리스트가 비어있는지 알려줌
     return __numItems == 0
    
 def size(): # 리스트의 총 원소 수 알려줌
     return __numItems

 def clear(): # 리스트 깨끗이 청소
     newNode.next = None 
     __head = newNode
     __numItems = 0

    연결 리스트의 구현

    여태까지 연결 리스트의 함수들을 알아보았는데요. 그렇다면 실제 연결 리스트 파이썬 코드 구현해보겠습니다.

    • listNode.py
     class ListNode:
     def __init__(self, newItem, nextNode: ‘ListNode’): # 새로운 ListNode 객체가 생성될 때 호출
     self.item = newItem
     self.next = nextNode

    이 클래스는 연결 리스트에서 노드를 생성하고 연결하는 데 사용됩니다. ‘newItem’은 노드가 저장할 데이터를 나타냅니다. ‘nextNode’는 다음 노드를 가리키는 참조입니다. 타입 힌트로 ‘ListNode’가 사용되었는데, 이는 ListNode 타입의 객체를 의미합니다. 문자열로 감싼 이유는 클래스 정의 전에 해당 타입이 아직 정의되지 않았기 때문입니다.

    self.item은 노드가 저장하는 데이터를 나타내는 인스턴스 변수입니다. 이 변수에 newItem 값을 할당합니다.

    self.next는 다음 노드를 가리키는 참조를 나타내는 인스턴스 변수입니다. 이 변수에 nextNode 값을 할당합니다.

    • linkedListBasic.py
     from DS.list.listNode import ListNode

 class LinkedListBasic:
     def __init__(self):
         self.__head = ListNode(‘dummy’, None)
         self.__numItems = 0

     def insert(self, i, newItem): …
     …
     def __getNode(self, i:int)->ListNode: …
     def printList(self): …

    내부에 있는 함수들은 위에서 실컷 언급했으므로 생략하겠습니다. 전체 코드는 교재에서 제공하고 있습니다.

    self.__head는 연결 리스트의 첫 번째 노드를 가리키는 참조를 나타내는 인스턴스 변수입니다.

    ListNode(‘dummy’, None)을 사용하여 더미 헤드 노드를 생성합니다.

    self.__numItems는 리스트의 항목 수를 나타내는 인스턴스 변수입니다. 초기값은 0으로 설정되어 리스트가 비어 있음을 나타냅니다.

최종적으로 지난번에 이야기했던(2달이나 지났지만…) 배열 리스트와 연결 리스트를 비교해보겠습니다.

배열 리스트

  • 직관적임
  • 인덱스가 주어지면 즉시 접근 가능함
  • 연속된 공간에 저장 되므로 삽입/삭제 시 시프트 작업이 필요
  • 오버플로우 시 배열을 새롭게 받아야함
  • 배열이 클수록 효율이 떨어짐

연결 리스트

  • 연속되지 않은 공간에 저장되어 링크를 관리해야 함
  • 인덱스가 주어지면 링크를 따라가야 함
  • 삽입/삭제 시 시프트 작업이 필요 없음
  • 원소가 추가될 때 동적을 공간 할당
  • 오버플로우로부터 자유로움
작업 배열 리스트 연결 리스트
insert(i) 위치 접근 (Θ(1)), 삽입 작업 (O(n)) 위치 접근 (O(n)), 삽입 작업 (Θ(1))
pop(i) 위치 접근 (Θ(1)), 삭제 작업 (O(n)) 위치 접근 (O(n)), 삭제 작업 (Θ(1))
remove(x) 원소 찾기 (O(n)), 삭제 작업 (O(n)) 원소 찾기 (O(n)), 삭제 작업 (Θ(1))
get(i) (Θ(1)) (O(n))

여기까지 연결 리스트에 대한 이야기를 해보았습니다. 다음에는 원형 연결 리스트에 대한 이야기로 다시 찾아오겠습니다!! 감사합니다😊😊