연결 리스트

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

 

 

노드란?

typedef struct {
    // 데이터
    int data;
    // 다음 노드의 포인터
    Node *next;
} Node;

 

연결 리스트의 구조

노드의 링크로 구성된다.
각 노드는 다른 메모리 Chunk에 저장된다.
시작 노드를 Head, 마지막 노드를 Tail이라고 한다.
Tail의 next 포인터는 NULL을 가리켜 끝임을 표시한다.

 

연결 리스트의 성능

원소 접근은 Head에서 시작하여 링크를 따라가야 하므로 O(n) 시간에 수행된다.
특정 원소를 알고 있을 때, 삭제 혹은 뒤에 원소를 추가하는 것은 O(1) 시간에 수행된다.
모든 노드가 다른 메모리 위치에 존재하므로 Cache locality (캐시 지역성)을 기대할 수 없다.
배열과 순차 접근의 시간 복잡도는 같지만 실제 성능은 떨어진다.

 

연결 리스트를 사용해야 할 때

원소의 개수가 유동적으로 변하는 경우
빈번한 삽입, 삭제가 발생하는 경우

• 작업 관리자의 프로세스 목록
• 웹 브라우저의 탭 목록 등

 

연결 리스트에서의 삽입

// p 노드 뒤에 원소 추가
void insertAfter(Node *p, int data)
{
    Node *newNode = new Node();
    newNode->data = data;

    newNode->next = p->next;
    p->next = newNode;
}

 

연결 리스트에서의 삭제

// p 노드의 다음 원소 삭제
void deleteAfter(Node *p)
{
    p->next = p->next->next;
    
    delete p->next;
}