블로그를 시작하는 이유는 여러가지가 있겠지만,
아무래도 자신이 공부한 것을 남들이 보기 편하게 정리하다 보면 본인도 다시 찾아보기 쉬워서인 것 같다.
아무튼 남과 나를 돕고자 블로그 활동을 시작하려고 한다.
오늘 간단히 정리할 내용은 연결 리스트라는 자료구조이다.
연결 리스트(linked list)의 정의 :
각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 자료구조.
라고 나와 있는데
여기서 포인터란 다음 노드의 주소를 말한다.
배열이랑 비교하면 둘 다 순서가 있는 자료구조지만
배열은 메모리상에 연속적으로 있어서 다음 주소를 'type크기'만큼 더해 알 수 있는 녀석이고
연결 리스트는 어떤 노드가 "내 다음 순서는 OO에 있는 노드야"라는 정보를 가지고 있는 것이다.
종류는 흔히 3가지가 있는데.
1. 단일 연결 리스트 : 다음 노드의 주소만 가지고 있다.
2. 이중 연결 리스트 : 다음 노드와 앞 노드의 주소도 가지고 있다.
3. 원형 연결 리스트 : 마지막 노드가 다음 노드의 주소로 첫번째 노드의 주소를 가지고 있다.
가장 기본적인 자료구조인 배열과 위와 같은 구현의 차이점 때문에 여러가지 차이가 생기는데...표로 보는게 편하다.
| 원소 크기 N | 배열 | 연결 리스트 |
| k번째 원소접근 | O(1) | O(k) |
| 임의 위치 원소 추가/제거 | O(N) | O(1) |
| 메모리 상의 배치 | 연속 | 불연속 |
| 추가 공간 | - | O(N) |
여기서 임의의 위치에 원소를 추가/제거하는 것은 행하는 위치의 주소가 주어져야 한다.(맨 앞, 뒤는 애초에 저장하고 있다)
연결 리스트에서는 데이터 말고도 다음 노드를 가리키는 주소가 추가적으로 저장되어야 해서 64bit컴퓨터에서 주소값이 64bit(8byte)라 8*N만큼의 추가 공간 즉 O(N)이 필요하다. (이중 연결 리스트의 경우 16*N)
혹시 O(N)등의 의미를 모르겠다면 인터넷에 빅오 표기법을 찾아보길 바란다.