[알고 공부] 0x04강 - 연결 리스트

출처: 바킹독 https://blog.encrypted.gg/93

 

 

 

 

2. 이중 연결 리스트

- STL에 연결 리스트가 있는데, 이 컨테이너의 이름은 list이고 구조는 이중 연결 리스트

 

3. 원형 연결 리스트

- 끝이 처음과 연결

- 각 원소가 이전과 다음 원소의 주소를 모두 들고 있어도 상관X

 

 

중요!!

 배열과 연결 리스트는 선형 자료구조

 

연결 리스트에서는 각 원소가 다음 원소, 혹은 이전과 다음 원소의 주소값을 가지고 있어야함 

32비트 컴퓨터면 주소값이 32비트(=4바이트) 단위 -> 4N 바이트가 추가로 필요

64비트 컴퓨터라면 주소값이 64비트(=8바이트) 단위 -> 8N 바이트가 추가로 필요

 

임의 위치에 원소 추가/제거 연산이 많은 경우, 연결리스트 사용을 고려

 

연결 리스트 정석 구현

NODE 구조체나 클래스를 만들어서 원소가 생성될 때 동적할당을 하는 방식

 

STL 사용 안되면 직접 구현해서 써야하는데 정석 구현은 코테에서 쓰기엔 별로

(면접 대비용으로 공부해놓긴해야해)

 

야매 연결리스트

원소를 배열로 관리하고 pre와 nxt에 이전/다음 원소의 포인터 대신 배열 상의 인덱스를 저장하는 방식

메모리 누수 문제로 실무에선 사용X 코테에선 시간복잡도도 같아서 사용O

dat[i] : i번지 원소의 값

pre[i] : i번지 원소에 대해 이전 원소의 인덱스

nxt[i] : 다음 원소의 인덱스

 

- pre나 nxt의 값이 -1이면 해당 원소의 이전/다음 원소가 존재하지 않는다

- unused는 현재 사용되지 않는 인덱스 => 새로 원소 추가가 가능한 인덱스. 원소 추가시 1씩 증가

- 특별히 0번지는 연결 리스트의 시작 원소로 고정 (값 들어가지 않고 단지 시작점을 나타내기 위한 dummy node)

=> 삽입 삭제 연산 시, 원소가 아예 없는 경우의 예외 처리가 덜 번거로워짐

 

연결 리스트의 모든 원소들을 출력

맨 마지막 원소의 뒤에 새 원소를 추가하는 상황이라면 "삽입할 위치의 다음 원소"가 존재하지 않음.

=> pre[-1] 접근 방지

pre[addr]은 더미노드 덕분에 -1이 아님이 보장되지만 nxt[addr]은 안댐

 

push_back, pop_back, push_front, pop_front는 모두 O(1)

iterator가 주소 역할

 03줄 : C++11 이상일 때 auto t = L.begin() 가능

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

순회를 할 때에는 C++11 이상이라면 12번째 줄과 같이 편하게 할 수 있지만, C++11 미만이라면 14, 15번째 줄처럼

STL list에서는 제일 뒤의 원소가 더미 노드

L.begin()은 제일 앞에 있는 원소를 가리키지만 L.end()는 제일 뒤에 있는 원소의 한 칸 뒤를 가리킨다