스킵리스트
-
[Data Structure] 연결 리스트와 스킵 리스트카테고리 없음 2020. 8. 11. 19:42
* 연결 리스트(Linked List) 연결 리스트는 일렬로 연결된 데이터를 저장할 때 사용하는 자료구조. 한 노드에는 다음 노드의 주소 정보가 담겨져 있다. 배열과 연결 리스트는 흔히 비교되는 자료구조 형태다. 배열의 경우에는 배열 각 칸들이 물리적으로 한 곳에 모여 있으므로, 크기를 한 번 정하면 늘리거나 줄일 수 없다. 반면, 연결 리스트의 경우 데이터를 중간에 삽입을 하는 것이 용이하다. 가령, A노드와 C 노드 사이에 B 노드를 추가하려는 경우, B 노드의 다음 주소를 C노드로 연결하고, A노드의 다음 주소를 B노드로 연결하면 된다. (관련 알고리즘 문제풀이) 연결 리스트는 주소를 일일이 찾아다녀야 하기 때문에 배열보다 검색 속도가 느릴 수 있다. 반면 위에서 본 것 처럼 데이터를 중간에 추가하..