[자료구조] 연결 리스트(Linked List)

연결 리스트(Linked List)

• 원소들을 저장할 때 그다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조이다.
• k번째 원소를 확인/변경하기 위해 O(k)가 필요하다.
• 임의의 위치에 원소를 추가, 제거는 O(1)
• 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉽다.

LinkedList 예시

 

연결 리스트의 종류

C++ STL 연결 리스트 list의 구조는 이중 연결 리스트이다.

• 단일 연결 리스트(Singly Linked List) : 각 원소가 자신의 다음 원소의 주소를 갖고 있다.
• 이중 연결 리스트(Doubly Linked List) : 각 원소가 자신의 이전 원소와 다음 원소의 주소 둘다를 갖고 있다.
• 원형 연결 리스트(Circular Linked List) : 끝이 처음과 연결되어있다.

 

배열 vs 연결 리스트

• 메모리 상의 배치는 배열은 연속, 연결 리스트는 불연속이다.
• 연결 리스트는 각 원소들이 이전과 다음 원소의 주소값을 가지고 있어야 하기 때문에 N에 비례하는 만큼의 메모리를 추가로 사용함.

 

C++ STL list

#include <iostream>
#include <list>
using namespace std;

int main(void) {

    list<int> L; 
    L.push_back(1); // 1
    L.push_back(2); // 2
    list<int>::iterator t = L.begin(); // t는 1을 가리킴
    
    L.push_front(10); //  10  (1)  2
    cout << *t << "\n"; // t가 가리키는 값인 1을 출력
    
    L.push_back(5);

    // t가 가리키는 곳 앞에 6을 insert
    L.insert(t, 6); // 10  6  1  2  5
    t++; // t는 2를 가리킴

    // t가 가리키는 값 제거, 그 다음 원소 5의 위치를 반환
    t = L.erase(t); // 10  6  1  (5)

    cout << *t << "\n"; // 5
    
    
    for (list<int>::iterator it = L.begin(); it != L.end(); it++)
        cout << *it << " "; // 10 6 1 5
        
    cout << "\n";
    for (auto data : L) 
        cout << data << ' '; // 10 6 1 5

    return 0;
}

 

 

<참고 자료>

baaaaaaaaaaaaaaaaaaaaaaarkingdog.tistory.com/932?category=773649