싱글링크드리스트

☝🏼 단일 연결 리스트 (Singly Linked List)

엘리베이터 없는 고층건물

헤드포인터, 테일포인터를 가지고 요소들을 연결만 하고있다.
즉 배열이랑 비교하면 삽입과 O(1)의 비용만 들어간다.

대신에 접근할 때(삽입, 삭제도 마찬가지) 해당 인덱스까지 순차적으로 가야하며
O(n)의 복잡도가 소요된다.

헤드와 테일일 데이터 삽입, 삭제 시 유리한 알고리

☝🏼 장점과 단점

장점

• 동적 크기: 런타임에 크기 조절 가능
• 메모리 효율성: 필요한 만큼만 메모리 할당
• 삽입/삭제 용이: 특정 위치에서의 삽입/삭제가 배열보다 효율적 (포인터만 변경)

단점

• 순차 접근만 가능: 랜덤 액세스 불가능
• 추가 메모리: 포인터 저장을 위한 오버헤드
• 캐시 지역성 부족: 메모리상에서 분산되어 있어 캐시 효율성 떨어짐

☝🏼 언제 연결리스트를 사용할까?

연결리스트가 유리한 경우:

• 데이터 크기가 자주 변할 때
• 맨 앞에서의 삽입/삭제가 빈번할 때
• 메모리가 제한적이고 동적 할당이 필요할 때
• 스택, 큐 구현시

배열이 유리한 경우:

• 랜덤 액세스가 필요할 때
• 캐시 성능이 중요할 때
• 수학적 연산이 많을 때
• 메모리 사용량을 최소화해야 할 때

☝🏼 빅오복잡도

선택

O(n) 이유는 링크드 리스트는 인덱스가 없기 때문에 해당 숫자까지 next포인터로 찾아야한다.

수정

O(n) 이유는 수정할 요소를 찾을때 선택해야하기때문이다.

삽입O(1)

맨 앞, 맨 뒤 삽입일경우 헤드와 테일의 포인터만 바꿔주면 되기때문에 O(1)이다 하지만 중간에 삽입하려 할경우 선택을 해야하기 때문에 O(n)이 될 수 있다.

삭제

O(1) 삽입과 유사하지만 꼬리 삭제에는 O(n) 복잡도가 요구된다.

☝🏼 이 외에 궁금한 점들

동적 크기가 좋은 이유는 뭘까?

• 예측 불가능한 데이터를 받기에 적합하다.
• 실제 사용한 만큼만 메모리를 사용하므로 메모리 낭비가 적다.
  • 반대로 추가 포인터를 사용하기 때문에 잘 짜여진 정적크기 프로그램보다 비효율적일 수 있다.

동적 크기의 단점

• 캐시성능 저하
• 오버헤드
• 메모리 단편화

동적 메모리가 쓰이는 예시

웹 서비스:

• 실시간 채팅 메시지 목록
• 동적 댓글 시스템
• 장바구니 아이템 관리
• 검색 결과 목록

시스템 프로그래밍:

• 프로세스/스레드 관리
• 네트워크 연결 풀
• 이벤트 큐
• 로그 수집기

정적 메모리가 쓰이는 예시

// 고성능이 필요한 수치 계산
const matrix = new Array(1000).fill(0).map(() => new Array(1000).fill(0));

// 임베디드 시스템에서 메모리 제한이 엄격한 경우
const sensorBuffer = new Array(100); // 정확히 100개만 필요

// 게임에서 60fps를 위한 최적화가 필요한 경우
const gameObjects = new Array(10000); // 미리 할당해서 GC 방지

☝🏼 싱글링크드리스트 구현 코드

class Node:
    # 생성자 (constructor)
    def __init__(self, val):
        # 인스턴스 속성 (instance attribute)
        self.val = val
        self.next = None

class SinglyLinkedList:
    def __init__(self): ## 링크드리스트 객체 초기화
        self.head = None
        self.tail = None
        self.length = 0

    """
        1. 새로운 노드를 생성
        2. 기존 꼬리의 next를 새로운 노드에 연결
        3. 새로운 노드를 꼬리로 지정
        O(1)
    """
    def push(self, val):
        newNode = Node(val)
        if not self.head:
            self.head = newNode
            self.tail = newNode  # 여기서 같은객체를 가르키므로 다음 코드에서는 헤드는 이 객체를 계속 가르키고 있다.
        else:
            self.tail.next = newNode
            self.tail = newNode
        self.length += 1
        return self

    """
        1. tail 제거
        2. next = null 이면 이전 것이 꼬리
        3. 이전 것.next = null
        O(n)
    """
    def pop(self):
        if self.length == 0:
            return None

        if self.length == 1:
            removed = self.head
            self.head = None
            self.tail = None
            self.length = 0
            return removed

        cur_node = self.head
        prev = cur_node
        while cur_node.next:
            prev = cur_node
            cur_node = cur_node.next
        # 루프를 빠져나오면 prev에는 꼬리-1
        # current_node= tail 이 위치
        self.tail = prev
        self.tail.next = None
        self.length -= 1

        return cur_node

    """
    새로운 노드를 헤드에 삽입
    포인터만 연결
    O(1)
    """
    def unshift(self, val):
        new_node = Node(val)
        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            cur_head = self.head
            self.head = new_node
            self.head.next = cur_head
        self.length += 1
        return self

    """
    헤드노드를 삭제 
    다음 노드가 헤드 역할
    O(1)
    """
    def shift(self):
        if self.length == 0:
            return None

        if self.length == 1:
            removed = self.head
            self.head = None
            self.tail = None
            self.length = 0
            return removed

        removed = self.head
        next_head = self.head.next
        self.head = next_head
        self.length -= 1
        return removed
    """
    해당 인덱스까지 순회
    O(n)
    """
    def get(self, index):
        if index < 0 or index >= self.length:
            return None
        count = 0

        if index == 0:
            return self.head
        if index == self.length - 1:
            return self.tail

        cur_node = self.head
        while count < index:  # index == 3
            cur_node = cur_node.next
            count += 1  # count == 3이 되었을때

        return cur_node
    """
    해당 인덱스까지 순회 후 수정
    O(n)
       """ 
    def set_value(self, index, value):
        found_node = self.get(index)
        if found_node:
            found_node.val = value
            return True
        return False

    """
    해당 인덱스까지 순회 후 삽입
    O(n)
    """
    def insert(self, index, value):
        if index < 0 or index > self.length:
            return False
        if index == 0:
            return True if self.unshift(value) else False
        if index == self.length:
            return True if self.push(value) else False

        new_node = Node(value)
        prev = self.get(index - 1)
        temp = prev.next
        prev.next = new_node
        new_node.next = temp
        self.length += 1
        return True
    """
    해당 인덱스까지 순회 후 제거
    O(n)
    """
    def remove(self, index):
        if index < 0 or index >= self.length:
            return False
        if index == 0:
            return True if self.shift() else False
        if index == self.length - 1:
            return True if self.pop() else False

        prev_node = self.get(index - 1)
        remove_node = prev_node.next
        prev_node.next = remove_node.next

        self.length -= 1
        return remove_node
    """
    헤드와 꼬리를 역순으로 재설정
    O(n)
    """
    def reverse(self):
        node = self.head
        self.head = self.tail
        self.tail = node

        next_node = None
        prev_node = None

        for _ in range(self.length):
            next_node = node.next
            node.next = prev_node
            prev_node = node
            node = next_node

        return self

    def __str__(self):
        """print() 함수용"""
        if self.length == 0:
            return "빈 리스트"

        values = []
        current = self.head
        while current:
            values.append(str(current.val))
            current = current.next
        return " -> ".join(values)