연결리스트, 랜덤접근과 순차적 접근

1. 연결리스트(linked list)

연결리스트는 노드로 감싸진 요소를 인접한 메모리 위치가 아닌, 독립적으로 저장하며 각 노드는 next 또는 next, prev라는 포인터로 서로 연결된 선형적인 자료구조

Data는 Node로 감싸져 있고, 가장 처음을 Head라고 한다.

 

2. 노드

노드는 단일 연결 리스트 기준으로 data, 그리고 노드와 노드를 잇게 만드는 next라는 포인터로 이루어져 있습니다.

class Node {
public:
    int data;
    Node* next; # 포인터
    Node(){
    	data = 0;
        next = NULL;
    }
    Node(int data){
    	this->data = data;
        this->next = NULL;
    }
};

 

연결리스트에서 삽입, 삭제는 O(1)의 시간 복잡도를 가진다. (연결을 끊고, 삽입하거나 제거한 후 연결하면 되기 때문)

연결리스트에서 접근, 탐색은 O(n)의 시간 복잡도를 가진다. (직접 접근이 안되고 1부터 n까지 접근해야하기 때문)

 

3. 이중연결리스트

이중연결리스트는 prev, next 두개의 포인터(양방향)으로 연결되어 있음

 

4. 원형연결리스트(Circular Linked List)

마지막 노드와 첫번째 노드가 연결되어 원을 형성, 싱글리스트 또는 이중연결리스트로 이루어진 2가지 타입의 원형연결리스트가 있음

  4-1. 원형싱글연결리스트 : Tail(끝)이 Head로 연결되어있는 구조

  4-2. 원형이중연결리스트 : Head -> Tail, Tail -> Head 모두 연결되어있는 구조

  4-3. c++ 예시 코드

#include <bits/stdc++.h>
using namespace std;
list<int> a;
void print(list <int> a) {
    for(auto it : a) cout << it << " ";
    cout << '\n';
}
int main() {
    for(int i = 1; i <= 3; i++) a.push_back(i); # 1 2 3
    for(int i = 1; i <= 3; i++) a.push_front(i); # 3 2 1
    
    auto it = a.begin(); it++;
    a.insert(it, 1000); # 3과 2사이에 1000을 삽입
    print(a); # 3 1000 2 1 1 2 3
    
    it = a.begin(); it++;
    a.erase(it); # 1000 제거
    print(a); # 3 2 1 1 2 3
    
    a.pop_front(); # 맨 앞 3 제거
    a.pop_back(); # 맨 뒤 3 제거
    print(a); # 2 1 1 2
    
    cout << a.front() << " : " << a.back() << '\n'; # 2 : 2
    a.clear(); # 연결리스트를 모두 소거
    return 0;
}

# 출력
# 3 2 1 1 2 3
# 3 1000 2 1 1 2 3
# 3 2 1 1 2 3
# 2 1 1 2
# 2 : 2

 

5. 랜덤접근과 순차적 접근

  5-1. 순차적 접근 : 시작부터 순차적으로 접근을 하는 자료구조

    ex:) linked list

    O -- O -- O --> O --> ... --> O // O(n) 시간복잡도

 

  5-2. 랜덤 접근 : 직접 접근이라고 하며, 임의의 인덱스에 직접 접근할 수 있는 자료구조

    ex:) array, vector

    a[3] => 4, a[100] => 5 // O(1) 시간복잡도

 

출처 : 인프런 강의, CS 지식의 정석 | 디자인패턴 네트워크 운영체제 데이터베이스 자료구조, 강사 : 큰돌