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

- 정의와 성질 -

연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

 

연결 리스트의 종류로는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있다.

이중 연결 리스트는 단일 연결 리스트와 달리 주어진 원소의 이전 원소를 알 수 있다. 다만 원소가 갖고 있어야 할 정보가 1개 더 많아져서 메모리를 더 많이 차지하게 된다.

원형 연결 리스트는 원소의 처음과 끝이 연결되어 있는 리스트이다.

 

배열과 달리 연결 리스트는 다음 원소의 주소 값 또는 이전 원소의 주소 값을 갖고 있어야 하기 때문에 64비트 컴퓨터라면 8N 바이트가 추가로 필요하다.

배열과 연결리스트는 메모리 상에 원소를 놓는 방식이 다르다고 해도 원소들 사이의 선후 관계가 일대일로 정의되어 있는 선형 자료구조이다. 면접에서 둘을 비교하는 구술시험이 나오기도 하니 정확하게 알아두자!

 

 

- 연결 리스트를 정석적으로 구현하는 방법 -

[ C ] 17. 연결리스트 구조체 ( Linked List ) (tistory.com)

[ C ] 17. 연결리스트 구조체 ( Linked List )

 

- 연결리스트를 배열로 구현하는 방법 -

메모리 누수 문제 때문에 실무에서는 절대 사용할 수 없지만 코딩 테스트에서는 사용 가능

dat[i]는 i번지 원소의 값, pre[i]는 i번지 원소의 이전 원소의 인덱스, nxt[i]는 다음 원소의 인덱스를 저장한다.

pre나 nxt 값이 -1이면 해당 원소의 이전 원소 혹은 다음 원소가 존재하지 않는다는 것을 의미한다.

unused는 현재 사용되지 않는 인덱스, 즉 새로운 원소가 들어갈 수 있는 인덱스 번호를 의미하고 원소가 추가될 때마다 1씩 증가한다.

여기서 연결리스트의 0번지는 값을 저장하지 않고 시작점을 나타내기 위한 dummy node로 사용된다.

 

시작 노드부터 가장 끝에 있는 노드를 만날 때까지 다음 노드로 이동하며 각 원소의 값을 출력하는 함수

 

unused 위치에 새로운 노드를 만들고 특정 원소(addr) 뒤에 연결시키는 함수

 

특정 위치(addr)에 있는 원소를 제거하는 함수

 

- STL 이중 연결 리스트 -

STL을 사용할 수 있는 상황이라면 연결리스트를 직접 구현하지 않고 사용하는 것이 훨씬 좋다.

push_back, push_front, pop_back, pop_front는 모두 O(1)의 시간복잡도를 가진다.

03번째 줄을 보면 여기서는 iterator가 주소 역할을 한다. list<int>::iterator대신 auto를 넣어도 된다. 

erase는 제거한 다음 원소의 위치를 반환한다.

C++11 미만이라면 12번째 줄처럼 범위 기반 반복문을 사용할 수 없고, 14번째 줄처럼 구현해야 한다.

 

 

🐶 바킹독의 실전 알고리즘 강의를 듣고 정리한 내용을 기록한 글입니다