[바킹독의 실전 알고리즘] 0x04강 - 연결 리스트

1. 정의와 성질

 

연결리스트란?

 

원소들을 저장할 때 그 다음 원소가 있는 위치 정보까지 포함시키는 방식으로 데이터를 저장하는 자료구조

 

연결리스트 성질

• k번째 원소를 확인/변경하기 위한 시간복잡도는 O(k)
  • 3 --- 73 ---- 88 로 연결된 연결리스트에서 3번째 원소 88을 찾고 확인하고 싶다면 3을 거치고 73을 거쳐 쭉 가야하므로 시간복잡도가 O(3)임을 알 수 있음

• 임의의 위치에 원소를 추가하거나 제거하는 데 시간복잡도는 O(1)

 

• 메모리 상에 원소들이 불연속적으로 배치되어 있어 Cache hit rate이 낮지만 할당은 쉬움

 

연결리스트 종류

 

 

참고로 STL에서 제공하는 연결 리스트 컨테이너 list에서 구현하는 연결 리스트는 이중 연결 리스트임!

그리고 세 번째 원형 연결 리스트에서 그림은 단일 연결 리스트 꼴로 표현했지만, 각 원소가 이전과 다음 원소의 주소를 모두 들고 있어도 상관이 없다고 함:)

 

 

📌 연결 리스트 VS 배열

배열과 연결 리스트의 공통점과 차이점, 또 그에 따른 장단점은 면접에서도 다뤄질 수 있다고 함. 면접이 아니더라도 코테에서 최적의 코드를 작성하기 위해서는 둘의 특징을 잘 알아두는 게 좋다고 함!

 

공통점 - 배열과 연결 리스트 모두 선형 자료구조에 속함.  

배열과 연결 리스트 모두 원소들 사이 선후 관계를 표현할 수 있음. (첫 번째 원소, 두 번째 원소, 세 번째 원소... 쭉 표현이 가능하니깐🤗) 따라서 이들은 선형 자료구조라고 할 수 있지만 이 후 배울 트리, 그래프, 해쉬 등은 비선형 자료구조임. 

 

차이점

 

	배열	연결 리스트
k번째 원소로 접근	O(1)	O(k)
임의 위치에 원소 추가 or 제거	O(N)	O(1) *엄밀히 말하면 상황이 좀 다르긴 함
메모리 상 배치	연속	불연속
추가로 필요한 공간(오버헤드)	-	O(N)

 

추가로 필요한 공간과 관련한 덧!

배열은 데이터를 저장하는 것 이외에 추가적으로 필요한 공간이 없음. 굳이 따지자면 길이 정보를 저장할 수 있는 int 1개가 필요하지만 너무 미미해서 무시해도 됨.

하지만 연결 리스트의 경우 모든 원소가 다음(혹은 이전의) 원소의 주소값을 가지고 있어야 함. 따라서 주소값의 크기에 따라 추가적으로 필요한 공간이 달라짐! 예를 들어 32비트 컴퓨터는 주소값이 32비트, 즉 4바이트이므로 4N 바이트가 추가로 필요함. 결론적으로 N에 비례하는 만큼의 메모리가 추가적으로 필요함.

 

2. 기능과 구현

 

기능

 

1) 임의의 위치에 있는 원소를 확인/변경 (시간복잡도 O(N))

연결 리스트 구조 상 처음부터 순차적으로 이동하면서 원소를 찾아야하기 때문에 평균적으로 N/2 시간이 걸려 시간복잡도는 O(N)

 

2) 임의의 위치에 원소를 추가 (시간복잡도 O(1))

3) 임의의 위치의 원소를 제거 (시간복잡도 O(1))

이 둘은 연결된 주소값만 바꾸면 되므로 시간복잡도는 O(1)... 이라고 하지만 만약 들어가기 전 원소의 주소를 모른다면 처음부터 쭉 찾아가야하기 때문에 엄밀히 말하면 O(1)은 아님

 

구현

 

정석적인 방법은 구조체나 클래스를 만들어서 원소가 생성될 때 동적할당을 하는 방식! (자료구조 때 배운 부분🤩)

 

하지만 우리 코테 준비하는 것이잖아요..?🙃

8282 민족 방식대로 가봅시다!

 

1) 야매 연결리스트 구현 -  원소들 & 주소들까지 각 배열에 저장하는 방법

배열로 모든 걸 구현하는 것이기 때문에 메모리 사용이 엄청나고, 쓸데없이 사용하는 부분도 많아 실무에서는 절대 사용 X

 

#include <bits/stdc++.h>
using namespace std;

const int MX = 1000005;
int dat[MX], pre[MX], nxt[MX];
//dat[i]는 i번째 원소 값, pre[i]는 i번지 이전 원소의 주소값, nxt[i]는 다음 원소의 주소값
int unused = 1; //현재 사용하지 않는 인덱스로 새로운 원소가 들어갈 수 있는 인덱스! 원소가 추가되면 +1
//0번지는 연결 리스트의 시작 원소로 항상 고정. 값이 들어가지 않고 시작점을 나타내는 dummy node

void insert(int addr, int num){
  dat[unused] = num;
  pre[unused] = addr;
  nxt[unused] = nxt[addr];
  if(nxt[addr] != -1) pre[nxt[addr]] = unused;
  nxt[addr] = unused;
  unused++;
}

void erase(int addr){
  nxt[pre[addr]] = nxt[addr];
  if(nxt[addr] != -1) pre[nxt[addr]] = pre[addr];
}

void traverse(){ //모든 원소 출력
  int cur = nxt[0]; //cur에 각 원소들 주소 담음
  while(cur != -1){
    cout << dat[cur] << ' ';
    cur = nxt[cur];
  }
  cout << "\n\n";
}

void insert_test(){
  cout << "****** insert_test *****\n";
  insert(0, 10); // 10(address=1)
  traverse();
  insert(0, 30); // 30(address=2) 10
  traverse();
  insert(2, 40); // 30 40(address=3) 10
  traverse();
  insert(1, 20); // 30 40 10 20(address=4)
  traverse();
  insert(4, 70); // 30 40 10 20 70(address=5)
  traverse();
}

void erase_test(){
  cout << "****** erase_test *****\n";
  erase(1); // 30 40 20 70
  traverse();
  erase(2); // 40 20 70
  traverse();
  erase(4); // 40 70
  traverse();
  erase(5); // 40
  traverse();
}

int main(void) {
  fill(pre, pre+MX, -1);
  fill(nxt, nxt+MX, -1);
  insert_test();
  erase_test();
}

 

insert 함수 원리

 

erase 함수 원리

 

 

2) STL에서 list 활용하기 (제일 best이지만 코테에서 드물게 STL 활용 안될 수도 있긴 함) 

 

#include <bits/stdc++.h>
using namespace std;

int main(void) {
  list<int> L = {1,2}; // 1 2
  list<int>::iterator t = L.begin(); // t는 1을 가리키는 중, iterator는 주소 역할임
  //C++11 이상일 때 auto t = L.begin()으로 써도 됨
  L.push_front(10); // 10 1 2
  cout << *t << '\n'; // t가 가리키는 값 = 1을 출력
  L.push_back(5); // 10 1 2 5
  L.insert(t, 6); // t가 가리키는 곳 앞에 6을 삽입, 10 6 1 2 5
  t++; // t를 1칸 앞으로 전진, 현재 t가 가리키는 값은 2
  t = L.erase(t); // t가 가리키는 값을 제거, 그 다음 원소인 5의 위치를 반환
                  // 10 6 1 5, t가 가리키는 값은 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 << ' ';
}

//STL에서 push_back, pop_back, push_front, pop_front는 모두 O(1)
/*야매 연결 리스트에서는 0번지, 즉 제일 앞에 원소를 더미 노드로 사용하지만 STL list에서는 제일 뒤의 원소가 더미임.
즉, L.begin()은 제일 앞에 있는 원소를 가리키고 L.end()는 제일 뒤에 있는 원소+1를 가리킴!!!!!*/