📚 리스트

데이터에 순서를 매겨 늘어놓은 자료구조

연결 리스트 (Linked List)

연결 리스트에서 각각의 원소를 노드(node)라고 한다. 노드는 데이터와 다음 노드를 가리키는(참조) 포인터를 가지고 있다.

노드 : 데이터 + 다음 노드 포인터

• 머리 노드(head node) : 리스트의 맨 앞에 위치한 시작 노드
• 꼬리 노드(tail node) : 맨 끝에 위치한 노드
• 앞쪽 노드(predecessor node) : 각 노드에서 바로 앞에 위치한 노드
• 뒤쪽 노드(successor node) : 각 노드에서 바로 뒤에 위치한 노드

연결 리스트 만들기

포인터

1) Node 클래스
Node는 데이터용 필드 data, 참조용 필드 next를 갖는다.

from __future__ import annotations
from typing import Any, Type

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

2) 연결 리스트 클래스

• no : 리스트에 등록되어 있는 노드의 개수
• head : 머리 노드에 대한 참조
• current : 현재 주목하고 있는 노드에 대한 참조

class LinkedList:
    def __init__(self) -> None:
        self.no = 0
        self.head = None
        self.current = None
    
    def __len__(self) -> int:
        return self.no

search()

def search(self, data: Any) -> int:
	cnt = 0
    ptr = self.head
    while ptr is not None:
    	if ptr.data == data:
        	self.current = ptr
            return cnt
        cnt += 1
        ptr = ptr.next
    return -1

...

포인터 방식은 노드를 삽입·삭제할 때 데이터를 이동하지 않고 처리한다.
이 방식은 노드를 삽입·삭제할 때마다 내부에서 노드용 인스턴스를 생성, 소멸하는데 이때 메모리 확보, 해제하는 데 필요한 비용을 무시할 수 없다.

커서

데이터 개수가 크게 변하지 않거나 데이터 최대 개수를 예측할 수 있는 경우라면 배열 안의 원소를 사용하여 효율적으로 운영할 수 있다.

연결 리스트를 배열로 구현할 때 배열 원소는 노드로, 데이터와 뒤쪽 노드의 인덱스로 구성된다.

노드 : 데이터 + 뒤쪽 노드 인덱스

• 뒤쪽 노드 인덱스를 커서라고 한다.
• head 인덱스 : 머리 노드의 인덱스 값(위치) = 커서
• 꼬리 노드 : 꼬리 노드의 커서는 -1이다.

커서 방식은 노드의 삽입과 삭제에 따른 원소 이동이 불필요하다는 장점이 존재한다. 그러나 반복적인 삭제로 인해 빈 배열의 수가 증가하게 된다.

프리 리스트

원형 이중 연결 리스트

원형 리스트 (Circular List)

연결 리스트의 꼬리 노드가 다시 머리 노드를 가리키는 모양의 리스트 구조

연결 리스트와 원형 리스트의 차이점
꼬리 노드의 뒤쪽 포인터가 None이 아니라 머리 노드의 포인터 값이 된다.

이중 연결 리스트

연결 리스트에서 뒤쪽 노드를 찾기 쉽지만 앞쪽 노드를 찾기 어렵다는 단점을 개선한 리스트 구조

각 노드에는 앞쪽 노드에 대한 포인터, 뒤쪽 노드에 대한 포인터 모두 주어진다.

Node 클래스

• data : 데이터에 대한 참조
• prev : 앞쪽 노드에 대한 참조
• next : 뒤쪽 노드에 대한 참조

원형 이중 연결 리스트

원형 리스트와 이중 연결 리스트를 결합한 자료구조!
즉, 머리 노드의 prev는 꼬리 노드를 참조하는 포인터이고, 꼬리 노드의 next는 머리 노드를 참조하는 포인터이다.