[자료구조] 임의 접근(Random Access)과 순차 접근(Sequential Access) 방식

여러 자료구조들이 메모리에 접근할 때

array처럼 index를 통해 바로 접근이 가능한 자료구조도 있고,

list처럼 맨 앞 원소부터 차례대로 찾아가야하는 자료구조가 있다.

이 방식을 각각 임의접근(Random Access)과

순차 접근(Sequentail Access)라고 부른다.

 

여기서 용어적으로 헷갈릴 수 있는데,

Random Access, Sequential Access는

하드웨어 메모리 장치인

RAM(Random Access Memory),

SAM(Sequential Access Memory)과는

다른 개념이니 헷갈리지 말자!

모든 자료구조에서 push한 데이터는 RAM에 올라간다.

 

Random Access : 임의 접근 방식

---

Random Access는 인덱스로 접근이 가능한 것을 의미하며 임의의 위치인 index를 알고있으면 arr[i]처럼 바로 그 위치로 접근하여 O(1)의 시간이 걸린다. 배열처럼 데이터가 연속된 메모리에 저장된다면 무조건 Random Access가 가능하다. 하지만 Random Access구조가 반드시 연속된 메모리에 할당되는 것은 아니다. 예를 들어 std::deque는 블록 기반으로 관리되지만, 인덱스 연산을 통해 O(1)접근을 제공한다. Random Access가 가능한 자료구조들은 포인터나 iterator를 통해 순차 접근까지 가능하다.

// array
int arr[5] = {10, 20, 30, 40, 50};
cout << "arr[2] = " << arr[2] << endl;  // O(1) 접근

// vector
vector<int> vec = {1, 2, 3, 4, 5};
cout << "vec[3] = " << vec[3] << endl;  // O(1) 접근

// deque
deque<int> dq = {100, 200, 300};
cout << "dq[1] = " << dq[1] << endl;    // O(1) 접근

랜덤 액세스 자료구조

• 연속 메모리 기반 Random Access 자료구조 : array, vector, string 등 연속 메모리라면 모두 임의 접근이 가능하다.
• 비연속 메모리 기반 Random Access 자료구조 : deque

 

 

Sequential Access : 순차 접근 방식

---

Sequential Access는 특정 위치에 접근하려면 포인터 연산이나 iterator를 통해 처음부터 차례대로 이동해야 도달할 수 있는 접근 방식을 말한다. 인덱스로 바로 접근할 수 없으며, 항상 한 단계씩 따라가야 하므로 n번째 원소에 접근하려면 O(n)의 시간이 걸린다. 보통 각 데이터들이 동적으로 할당되어 연속된 메모리에 위치하지 않는 자료구조들이 순차 접근 방식만 가능하다. 순차 접근 방식의 자료구조들은 deque처럼 별도의 인덱스를 관리하지 않는 한 Random Access가 불가능하다.

 

// list
list<int> lst = {10, 20, 30};
for(auto it = lst.begin(); it != lst.end(); ++it) {
    cout << *it << " ";  // 순차 접근
}
cout << endl;

// stack
stack<int> st;
st.push(1); st.push(2); st.push(3);
while(!st.empty()) {
    cout << st.top() << " "; // 순차 접근 (top에서 pop)
    st.pop();
}
cout << endl;

// map
map<int, string> mp = {{1, "one"}, {2, "two"}, {3, "three"}};
for(auto it = mp.begin(); it != mp.end(); ++it) {
    cout << it->first << ":" << it->second << " ";  // 순차 접근 (key 순서)
}
cout << endl;

시퀀셜 액세스 자료구조

• stack, queue, list, map, set

 

 

 

Random Access와 Sequential Access는

메모리에 접근하는 방식을 나타내는 개념이며

이 둘은 배타적이지 않다.

 

위에서 얘기 했듯이

Random Access가 가능한 자료구조들은

포인터나 iterator를 통해

원소를 차례대로 이동하는 순차 접근까지 가능하다.

예를 들어 vector는 동적 배열이므로

연속된 메모리에 할당되어 Random Access도 가능하고,

포인터 연산을 통해 순차 접근도 가능하다.

 

하지만 반대의 경우는 불가능하다!

왜냐하면 순차 접근만 가능한 자료구조들은

대부분 데이터들이 메모리의 연속되지 않은 공간에 할당되어있기 때문에

포인터 연산으로 얼마만큼의 메모리 주소를 증가시켜야하는지

알 수 없기 때문이다.

(deque처럼 별도의 인덱스를 관리하고있다면 가능하다.)