자료구조 (연결 리스트)

연결 리스트(Linked List)

연결 리스트란 노드를 연결시킨 자료구조를 말하며 여기서 노드란 연결 리스트에서 데이터를 갖고 있는 데이터의 묶음을 말한다

연결 리스트에 삽입/삭제 속도는 O(1)이고 탐색 속도는 O(N)으로 삽입/삭제 속도가 빠르며 탐색 속도는 느리다고 볼 수 있다

이러한 까닭을 그림으로 보면

우선 탐색은

위와 같이 연결 리스트는 배열과 달리 값이 메모리 상에 연속적으로 있지 않고 데이터 값과 다음 노드에 주소 값으로 이루어졌기에 배열처럼 인덱스 값으로 한번에 찾는게 불가능하여 값을 찾으려면 노드를 타고 타고 가야하기에 느리다

그리고 삽입/삭제는

위와 같이 연결된 메모리 주소만 바꾸면 되기에 빠르다

C++ 코드로는 이렇게 구현할 수 있다

list<int> l;

l.emplace_back(0);
l.emplace_back(1);
l.emplace_back(2);
l.emplace_back(3);

cout << "size: " << l.size() << "\n";

for (auto i:l) {
    cout << i << "\n";
}