더북(TheBook)

3.4 연결 리스트

연결 리스트(linked list)는 동적 자료 구조로, 메모리를 실행 시간에 할당합니다. 연결 리스트는 연속적으로 자료를 저장하지 않고 다음 원소를 가리키는 링크를 사용합니다.

▲ 그림 3-2 연결 리스트

연결 리스트는 원소에 직접 접근할 수 없어서 성능이 배열보다 느립니다. 하지만 저장할 원소의 개수를 미리 알지 못할 때 유용합니다. 연결 리스트에는 선형(linear), 원형(circular), 이중(doubly), 이중 원형(doubly circular) 등 많은 종류가 있습니다.

연결 리스트의 API는 다음과 같습니다.

Insert(k) 리스트의 맨 앞에 k를 추가합니다. 리스트의 맨 앞에 새 원소를 삽입하고 포인터를 이동합니다. 새 원소는 리스트의 첫 번째 원소가 됩니다. 이 연산은 상수 시간 O(1)에 수행됩니다.

Delete() 리스트의 첫 번째 원소를 삭제합니다. 리스트의 첫 번째 원소를 삭제하려면 포인터만 이동하면 됩니다. 이 연산은 상수 시간 O(1)에 수행됩니다.

PrintList() 리스트의 모든 원소를 표시합니다. 첫 번째 원소부터 시작해서 다음 포인터를 따라 갑니다. 이 연산은 O(n) 시간에 수행됩니다.

Find(k) 값이 k인 원소의 위치를 찾습니다. 첫 번째 원소부터 시작해서 찾는 값을 발견하거나 리스트의 끝에 도달할 때까지 다음 포인터를 따라갑니다. 이 연산은 O(n) 시간에 수행됩니다.

FindKth(k) k번째 위치의 원소를 찾습니다. 첫 번째 원소부터 시작해서 k번째 원소에 도달할 때까지 노드(node)의 다음 연결(link)을 따라갑니다. 이 연산은 O(n) 시간에 수행됩니다.

IsEmpty() 원소가 없는 빈 리스트인지 확인합니다. 리스트의 헤드 포인터만 확인합니다. Null 값을 가지면 빈 리스트고 아니면 빈 리스트가 아닙니다. 이 연산은 O(1) 시간에 수행됩니다.

Note ≡


이진 검색은 연결 리스트에서 작동하지 않습니다.

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.