Linked List와 Array, 그리고 Swift에서의 Array.

Linked List

• 여러 구조체 인스턴스를 Chain처럼 줄줄이 포인터로 연결한 자료구조(선형, 일차원 형태)
• 연결에 사용된 포인터 숫자가 한개이고 자기 다음을 가리키는 것이 특징

 

 

구현하기(c++)

• Node는 데이터를 담기위한 컨테이너가 됨.
• (next)포인터를 이용해서 다른 노드를 포인팅함.
• nullptr를 가진 노드가 마지막 노드가 됨.

#include <iostream>

// 노드 구조체 정의
struct Node {
    int data;
    Node* next;

    Node(int data) : data(data), next(nullptr) {}
};

// 단일 연결 리스트 클래스 정의
class SingleLinkedList {
public:
    Node* head;

    SingleLinkedList() : head(nullptr) {}

    // 리스트에 노드를 추가하는 메서드
    void insert(int data) {
        Node* newNode = new Node(data);

        if (head == nullptr) {
            head = newNode;
        } else {
            Node* current = head;
            while (current->next != nullptr) {
                current = current->next;
            }
            current->next = newNode;
        }
    }

    // 리스트에서 노드를 제거하는 메서드
    void remove(int data) {
        if (head == nullptr) return;

        if (head->data == data) {
            Node* temp = head;
            head = head->next;
            delete temp;
            return;
        }

        Node* current = head;
        while (current->next != nullptr) {
            if (current->next->data == data) {
                Node* temp = current->next;
                current->next = current->next->next;
                delete temp;
                return;
            }
            current = current->next;
        }
    }

    // 리스트 내용을 출력하는 메서드
    void print() {
        Node* current = head;
        while (current != nullptr) {
            std::cout << current->data << " -> ";
            current = current->next;
        }
        std::cout << "NULL" << std::endl;
    }
};

출력해보기

int main() {
    SingleLinkedList list;

    list.insert(1);
    list.insert(2);
    list.insert(3);

    std::cout << "Initial list:" << std::endl;
    list.print();

    list.remove(2);
    std::cout << "List after removing 2:" << std::endl;
    list.print();

    return 0;
}

• 배열(Array)과 연결 리스트(Linked List)의 차이점은 무엇?
  • Array
    • 메모리에서 연속적인 공간을 차지
    • 배열의 크기는 정적, 크기를 변경하려면 새로운 메모리 영역에 배열을 복사 → 단점?
    • 인덱스를 사용하여 O(1) 시간 내에 임의의 요소에 접근 → 장점
    • 삽입 또는 삭제 작업 시, 해당 위치 이후의 모든 요소를 이동해야 하므로 최악의 경우 O(n) 시간이 소요 → 단점
  • LinkedList
    • 개별 요소가 메모리의 비연속적인 위치에 저장
    • 각 요소가 다음 요소에 대한 참조(주소)를 포함
    • 연결 리스트의 크기는 동적 → 장점
    • 특정 요소에 접근하려면 연결된 노드를 차례로 탐색해야 하므로 O(n) 시간이 소요 → 단점
    • 삽입 및 삭제 작업 시, 단지 참조를 변경하면 되므로 O(1) 시간이 소요. → 장점 단, 삭제할 요소를 찾기 위해 리스트를 탐색해야 하는 경우에는 O(n) 시간이 소요
    • 각 요소는 값과 다음 요소에 대한 참조를 저장해야 하므로 추가적인 메모리 오버헤드가 발생 → 단점

오버헤드 : 어떤 프로세스를 수행하거나 기능을 제공하는 데 필요한 추가적인 자원이나 작업을 의미

• Swift 배열
  • Swift의 배열은 Dynamic Array로 배열의 크기를 실행 중에 동적으로 조정할 수 있다.
  • ex) C++ Vector, JAVA ArrayList
  • Linked List와 마찬가지로 동적 배열은 고정된 크기의 배열보다 유연하게 사용할 수 있지만, 크기 변경에 따른 오버헤드가 발생
  • 그렇다면 **Dynamic Array**과 LinkedList는 같은 것인가?
    • 메모리 관점
      • 동적 배열: 메모리에서 연속적인 공간을 차지하며, 요소를 추가하거나 삭제할 때 크기가 자동으로 확장되거나 축소 메모리 오버헤드가 일반적으로 X. 값만 저장되기 때문
      • 연결 리스트: 메모리에서 비연속적인 공간을 차지하며, 각 요소가 다음 요소에 대한 참조(주소)를 포함합니다. 메모리 오버헤드가 발생
    • 참조 시
      • 동적 배열: 인덱스를 사용하여 O(1) 시간 내에 임의의 요소에 접근할 수 있습니다.
      • 연결 리스트: 특정 요소에 접근하려면 연결된 노드를 차례로 탐색해야 하므로 O(n) 시간이 소요됩니다.
    • 추가, 삭제 시
      • 동적 배열 : 최악의 경우 O(n)
      • 연결 리스트: O(1)
• 참조
  • C 로배우는 자료구조 강의(널널한 개발자)
  • chatGPT