배열과 달리 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움
연결리스트의 종류
단일 연결 리스트 : 원소가 ‘다음’원소의 주소를 알고 있다.
이중 연결 리스트 : 원소가 ‘이전’원소의 주소와 ‘다음’원소의 주소를 둘 다 알고 있다.
원형 연결 리스트 : 마지막 원소가 가장 처음원소의 주소를 알고 있다.
배열과 연결리스트 비교
배열은 원소의 값만 저장한다. 반면에 연결리스트는 '다음 원소의 주소'도 저장하므로 메모리를 더 필요로 한다.
연결리스트를의 시간복잡도를 정리하면,
임의의 위치에 있는 원소를 확인하거나 변경 = O(N) 임의의 위치에 원소를 추가/ 임의 위치의 원소를 제거 = O(1) (추가할 주소를 알고 있는 경우, O(1)에 가능하다는 의미다. )
배열에 비해, ‘다음 주소’만큼의 메모리를 소모한다.
그래서 32비트 컴퓨터면 주소값이 32비트(=4바이트) 단위이니 4N 바이트가 추가로 필요하다. 64비트 컴퓨터라면 주소값이 64비트(=8바이트) 단위이니 8N 바이트가 추가로 필요하게 된다. 즉 N에 비례하는 만큼의 메모리를 추가로 쓰게 된다.
0x01 기능과 구현
기능
임의의 위치에 있는 원소를 확인하거나 변경 = O(N) 임의의 위치에 원소를 추가/ 임의 위치의 원소를 제거 = O(1)
어디에 연결리스트가 어디에 활용될까 ?
메모장! 을 예로 들 수 있다. 커서를 옮기고, 글자를 지우고 이러한 변경 연산이 많다. 이렇게 추가 제거 연산이 자주 발생하는 경우 연결리스트 사용을 고려해보자.
구현
STL에서 제공하는 list를 쓰자. STL에 연결리스트가 있는데, 이 컨테이너의 이름은 list이고 내부적으로 Double Linked List로 구현되어 있다. 면접에서의 손코딩을 대비할 때 STL list를 이용해서 끄적이며 연습하자.
정석적인 구현
NODE 구조체나 클래스를 만들어서 원소가 할당될 때마다 동적할당을 하고, 노드를 삭제하면 메모리를 해제하는 식으로 구현한다.
struct NODE{
struct NODE *prev, *next;
int data;
};
야매 연결 리스트
STL의 list가 제공되지 않는 경우에 임시로 쓰는 연결리스트 형태를 배운다 . 메모리 할당 및 해제를 생략하고 배열만을 이용한다. 메모리 누수 문제 때문에 실무에서는 절대 쓸 수 없다. 구현 난이도가 일반적인 연결리스트보다 낮고, 시간복잡도도 동일하므로 코테에서만 애용하면 된다.
메모리 할당 및 해제를 생략한 형태
야매 연결리스트는 원소를 배열로 관리한다.
이전/다음 원소 주소를 가리키는 대신, 배열 인덱스를 저장하는 방식으로 구현한 연결리스트다.
dat 배열 : 데이터 저장 pre 배열 : 이전 노드의 주소 저장 nxt 배열 : 다음 노드의 주소 저장 unused: 새로운 원소가 들어갈 수 있는 인덱스. 원소가 추가되면 1씩 증가한다. 0번지: 시작점을 나타내기 위한 dummy node. 실제로 값을 저장하지 않는다.
pre 값이나 nxt 값이 -1이면 해당 원소의 이전/다음 원소가 존재하지 않는다는 의미다.
모든 노드를 순회하여 출력하는 traverse() 함수
0번지 (dummy node)에서 시작한다.
더미노드가 가리키는 nxt는 2 인덱스를 가리킨다.
따라서 더미노드 다음 노드는 2번지 노드다.
void traverse(){
int cur = nxt[0];
while(cur != -1){
cout << dat[cur << ' ';
cur = nxt[cur];
}
cout << '\n';
}
#include <bits/stdc++.h>
using namespace std;
const int MX = 1000005;
int dat[MX], pre[MX], nxt[MX];
int unused = 1; // 사용가능한 인덱스
void insert(int addr, int num){ // 삽입하려는 인덱스와 값을 파라미터로 받는다.
dat[unused] = num; // 새로운 원소를 생성
pre[unused] = addr; // 이전 노드의 다음 인덱스에 현재 삽입하려는 인덱스를 대입
nxt[unused] = nxt[addr]; // 새 원소의 nxt값에 삽입할 위치 nxt 값을 대입
if(nxt[addr] != -1) pre[nxt[addr]] = unused; // 맨 마지막 원소에 데이터를 추가할 때를 처리.
nxt[addr] = unused; // 삽입한 인덱스의 다음은 unused
unused++; // 새로 할당할 수 있는 인덱스 증가시키기
}
void erase(int addr){
nxt[pre[addr]] = nxt[addr]; // 이전 노드의 nxt에 삭제할 노드의 nxt할당.
if(nxt[addr] != -1) pre[nxt[addr]] = pre[addr]; // 삭제할 노드가 마지막이 아닌 경우 처리.
}
왜 pre[addr]이 -1인지는 체크를 하지 않아도 되는데 nxt[addr]이 -1인지는 체크를 해야 할까?
더미노드가 존재하니까 pre[addr]는 항상 -1이 아니다. 맨 마지막 원소일 경우 nxt[addr]가 -1일 수 있기 때문이다.
0x02 STL list
vector와 비슷한 것이 많다.
push_back, pop_back, push_front, pop_front는 모두 O(1)의 시간복잡도다.
iterator가 주소 역할을 한다! 매우 유용함.
int main(void) {
ios_base::sync_with_stdio(0);
cin.ignore(0);
list<int> L = {1, 2}; // 1, 2
list<int>::iterator t = L.begin(); // t는 1을 가리킨다.
L.push_front(10); // 10, 1, 2
cout << *t << '\n'; // t는 1을 가리키니까, 1이 출력된다.
L.push_back(5); // 10, 1, 2, 5
L.insert(t, 6); // t가 가리키는 곳 앞에 6을 삽입한다. 10, 6, 1, 2, 5
t++; // t를 한 칸 뒤쪽으로 보낸다. t는 2를 가리킨다.
t = L.erase(t); // t가 가리키는 값을 제거하고, 그 다음 원소의 위치를 반환한다.
// 2를 제거하고 t는 5를 가리키게 된다. 10, 6, 1, 5
cout << *t << '\n'; // 5
// 순회하며 출력
for(auto i : L) cout << i << ' ';
cout << '\n';
for(list<int>::iterator it = L.begin(); it != L.end(); it++)
cout << *it << ' ';
return 0;
}
list::iterator라는 type을 치기가 귀찮으면 C++11 이상일 때 auto t = L.begin()으로 써도 된다.
손코딩 문제 1 원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때, 해당 리스트의 길이를 효율적으로 구하는 방법?
정답 동일한 노드가 나올때 까지 계속 다음 노드로 가면 됨. 공간복잡도 O(1) 시간복잡도 O(N)
손코딩문제 2 중간에 만나는 두 연결 리스트의 시작점들이 주어졌을 때, 만나는 지점을 구하는 방법은?
정답 일단 각 리스트의 길이를 구한다. 더 긴 리스트에서 둘의 길이 차이 만큼 앞으로 이동시켜 놓는다. 두 시작점이 만날 때 까지 두 시작점을 동시에 한 칸씩 전진 시키면 된다.
손코딩문제 3 주어진 연결 리스트 안에 사이클이 있는지 판단하라.
정답 Floyd’s cycle-finding algorithm, 공간복잡도 O(1), 시간복잡도 O(N) 한 칸씩 가는 커서와 두 칸씩 가는 커서를 동일한 시작점에서 출발시킨다. 사이클이 없으면, 두 커서가 만나지 못하고 연결리스트의 끝에 도달한다. 사이클이 있으면, 두 커서는 반드시 만나게 된다. 거치는 모든 노드를 저장할 필요가 없다.
#include <bits/stdc++.h>
using namespace std;
list<char> strList;
string str;
int M;
char ch, x;
void input(){
cin >> str >> M; // 초기 문자열, 명령의 횟수
// 문자열의 문자를 리스트에 넣는다.
for(int i = 0; i < str.size(); i++){
strList.push_back(str[i]);
}
auto cur = strList.end(); // 커서는 마지막을 가리키고 있다
while(M--){ // 명령 수행
cin >> ch;
if(ch == 'P') {
cin >> x;
strList.insert(cur, x); // 문자를 커서 왼쪽에 추가
}
else if(ch == 'L') {
if (cur != strList.begin()) { // 맨 처음이 아니면,
cur--; // 커서를 왼쪽으로 한 칸 옮김
}
}
else if(ch == 'D'){
if(cur != strList.end()){ // 커서가 맨 마지막이 아니면,
cur++; // 커서를 오른쪽으로 한 칸 옮김
}
}else { // 'B'
if(cur != strList.begin()){ // 커서가 맨 마지막이 아니면,
cur--; // 커서 기준 왼쪽이니까 -- 해준다.
cur = strList.erase(cur); // 문자 삭제 후, 주소값을 갱신
}
}
}// while
for(auto c : strList) cout << c;
}
int main(void) {
ios_base::sync_with_stdio(0);
cin.ignore(0);
input();
return 0;
}
Stack 을 이용한 "맞았습니다"코드
#include <bits/stdc++.h>
using namespace std;
stack<char> leftStack;
stack<char> rightStack;
string str;
int M;
char ch, x;
void input(){
cin >> str >> M;
for(int i = 0; i < str.size(); i++){
leftStack.push(str[i]);
}
while(M--){ // 명령 횟수만큼 반복
cin >> ch; // 명령 문자
switch(ch){
case 'P':
cin >> x; // 추가할 문자
leftStack.push(x); // 문자를 커서 왼쪽에 추가
break;
case 'L':
if(!leftStack.empty()){ // 왼쪽 스택에 문자가 있는지 확인
rightStack.push(leftStack.top()); // 왼쪽 스택에 있던 top을 오른쪽 스택에 넣는다
leftStack.pop(); // 실제 pop()연산 수행
}
break;
case 'D':
if(!rightStack.empty()){ // 커서 오른쪽에 문자가 있는지 확인
leftStack.push(rightStack.top());
rightStack.pop();
}
break;
case 'B':
if(!leftStack.empty()){
leftStack.pop();
}
break;
}// switch
}// while
while(!leftStack.empty()){ // 문자를 순서대로 꺼내야 하니까. 왼쪽스택에 있던것을 오른쪽으로 전부 이동시킴
rightStack.push(leftStack.top());
leftStack.pop();
}
while(!rightStack.empty()){ // 실제 답 출력
cout << rightStack.top();
rightStack.pop();
}
}
int main(void) {
ios_base::sync_with_stdio(0);
cin.ignore(0);
input();
return 0;
}
연결리스트를 이용한 경우 리뷰
커서의 위치를 저장하기 위해 iterator를 이용했다.
auto cur = strList.end(); // 커서는 마지막을 가리키고 있다
erase 함수로 커서가 가리키는 문자를 삭제하고 나서, 커서의 주소를 갱신해주는 것을 유의해야 한다.
cur = strList.erase(cur); // 문자 삭제 후, 주소값을 갱신
스택을 이용한 경우 리뷰
커서를 기준으로 두고 스택을 2개 사용했다.
커서를 기준으로 왼쪽에 저장할 문자를 담을 스택, 커서를 기준으로 오른쪽에 저장할 문자를 담을 스택.
