LinkedList – Single

연결 리스트의 필요성

1) 일반적으로 배열을 사용하여 데이털르 순차적으로 저장하고, 나열할 수 있다.
2) 배열을 사용하는 경우 메모리 공간이 불필요하게 낭비 될 수 있다.

---

배열 기반 리스트의 특징

1. 배열로 만들었으므로 특정 위치 원소에 즉시 접근 가능하다.
2. 데이터가 들어갈 공간을 미리 메모리에 할당해야 하는 단점이 있다.
3. 원하는 위치로 삽입이나 삭제가 비효율적이다. -> 주소를 당기고 밀어야하기 때문에.

---

연결리스트의 조건

1. 연결 리스트는 구조체와 포인터를 함께 사용하여 구현한다.
2. 연결 리스트는 리스트의 중간 지점에 노드를 추가하거나 삭제할 수 있어야 한다.
3. 필요할 때마다 메모리 공간을 할당 받는다.

연결리스트의 특징

1) 삽입과 삭제가 배열에 비해서 간단하다.
2) 배열과 다르게 특정 인덱스로 즉시 접근하지 못하며, 노드를 차례대로 들어가야 한다
3) 노드의 포인터 사용에 대한 코스트 고려.

배열이 강점일때

• 인덱스 참조

---

단일 연결 리스트

1. 단일 연결 리스트는 다음과 같은 형태로 나타낸다.
2. 포인터를 이용해 단방향적으로 다음 노드를 가리킨다.
3. 연결 리스트의 시작 노드를 헤드하고 한다.
4. 다음노드가 없는 끝 노드의 경우 다음 포인터에 NULL이 들어간다.

연결리스트의 기본 형태

• 연결리스트의 클래스

from __future__ import annotations
from typing import Any

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

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

    def __len__(self) -> int:
        return self.no

연결리스트의 노드 탐색

def search(self, data: Any) -> int:
    count = 0
    pointer = self.head
    while pointer is not None:
        if pointer.data == data:
            self.current = pointer
            return count
        count += 1
        pointer = pointer.next
    return -1
def __contains__(self, data: Any) -> bool:
    """ implementation 'in' """
    return self.search(data) >= 0

연결리스트의 맨 앞에 노드 삽입

def add_first(self, data: Any) -> None:
    pointer = self.head
    self.head = self.current = Node(data, pointer)
    self.volume += 1

연결리스트 맨 끝에 노드 삽입

def add_last(self, data: Any) -> None:
    if self.head is None:
        self.add_first(data)
    else:
        pointer = self.head
        while pointer.next is not None:
            pointer = pointer.next
        pointer.next = self.current = Node(data, None)
        self.volume += 1

연결리스트의 맨 앞 노드 삭제

def remove_first(self) -> None:
    if self.head is not None:
        self.head = self.current = self.head.next
    self.volume -= 1

연결리스트의 맨 끝 노드 삭제

def remove_last(self) -> None:
    if self.head is not None:
        if self.head.next is not None:
            self.remove_first()
        else:
            pointer = self.head
            previous_pointer = self.head

            while pointer.next is not None:
                previous_pointer = pointer
                pointer = pointer.next

            previous_pointer.next = None
            self.current = previous_pointer
            self.volume -= 1

연결리스트의 모든 노드 출력

---