각 원소가 값과 다음 원소의 위치를 가리키는 포인터를 가지며, 그것을 따라가며 이어지는 자료 구조. 위치를 알고 있으면 삽입이나 삭제는 포인터를 바꿔 다는 것으로 O(1)이지만, i번째 원소를 읽으려면 앞에서부터 따라가는 O(n)이 필요하다. 원소가 메모리 위에 흩어지기 쉬워 배열보다 캐시가 잘 듣지 않는다.
일본어 명칭: 連結リスト
연결 리스트(Linked List)은(는) 자료 구조와 알고리즘, 메모리 계층 구조, 프로그래밍의 기초(의사 코드 트레이스) 등 5개 분야의 연습 문제 10개에 나와요.
분야: 자료 구조와 알고리즘
정답: A. 삽입할 위치 바로 앞의 원소를 알고 있으면 다른 원소를 옮기지 않고 포인터를 바꿔 다는 것만으로 삽입할 수 있지만, i번째 원소를 읽으려면 앞에서부터 차례로 따라가야 한다
연결 리스트에서는 삽입이나 삭제할 위치를 알고 있으면 앞뒤의 포인터를 바꿔 쓰기만 하면 되므로 O(1)로 끝납니다. 한편 i번째 원소를 읽으려면 맨 앞에서부터 i번 포인터를 따라가야 하므로 O(n)이 걸립니다. 배열은 시작 주소와 원소의 크기로 i번째 주소를 계산할 수 있으므로 O(1)로 읽을 수 있지만, 중간에 삽입하려면 뒤쪽 원소를 밀어내는 O(n)의 수고가 듭니다. 또한 배열은 원소가 연속해서 늘어서므로 캐시나 프리페치가 잘 듣고, 메모리 위에 흩어지기 쉬운 연결 리스트는 같은 O(n)의 순회라도 훨씬 느려지는 경우가 있습니다.
정답: A. 체이닝에서는 적재율이 1을 넘어도 저장할 수 있지만, 개방 주소법에서는 표의 크기를 넘어 저장할 수 없고, 적재율이 1에 가까워지면 탐색 횟수가 급격히 늘어난다
체이닝은 같은 위치의 원소를 리스트로 이으므로 원소 수가 표의 크기를 넘어도 저장할 수 있지만, 리스트의 평균 길이는 적재율에 비례하여 늘어나고 탐색의 수고도 늘어납니다. 개방 주소법은 표 안에만 저장하므로 원소 수는 표의 크기까지이며, 적재율이 1에 가까워지면 빈자리를 찾는 횟수가 급격히 늘어납니다. 어느 방법이든 적재율이 정해 둔 값(예를 들어 0.5~0.75 정도)을 넘으면 표를 키워서 모든 원소를 다시 넣는(재해싱) 것이 보통입니다. 개방 주소법에서도 충돌은 일어나며, 빈 위치를 찾는 것으로 대처하고 있습니다.
연결 리스트에서는 다음 요소의 주소를 p->next를 읽어야 비로소 알 수 있습니다.
위 연결 리스트를 따라가는 처리가 같은 수의 요소를 가진 배열을 차례로 읽는 것보다 크게 느려지기 쉬운 이…연결 리스트에서는 삽입이나 삭제할 위치를 알고 있으면 앞뒤의 포인터를 바꿔 쓰기만 하면 되므로 O(1)로 끝납니다.
배열과 비교했을 때 연결 리스트(각 원소가 다음 원소의 위치를 가리키는 포인터를 가진 리스트)의 특징으로 …연결 리스트의 연결을 바꿀 때는 뒤쪽 요소로 가는 경로를 잃지 않는 순서로 대입합니다.
다음 프로그램은 배열 next로 연결한 연결 리스트 A → C → E → D → B의 "C"(인덱스 3) …연결 리스트는 다음 요소의 주소를 현재 요소를 읽을 때까지 알 수 없으므로 규칙성이 없어 예측할 수 없습니다.
하드웨어 프리페치가 특히 효과를 발휘하기 쉬운 접근은?연결 리스트의 선두 포인터가 A일 때, 어떤 스레드가 A를 읽고 CAS를 준비하는 사이에 다른 스레드가 A를 제거하고 B에 대한 조작을 한 뒤, 다시 같은 주소 A의 노드를 넣는 경우가 있습니다.
CAS를 사용한 락프리 자료 구조에서 문제가 되는 ABA 문제에 대한 설명으로 올바른 것은 무엇입니까?배열(Array) 프리페치(Prefetch) 포인터(Pointer) 해시 테이블(Hash Table) 캐시 라인(Cache Line) 시간 복잡도(Time Complexity) ABA 문제 LR/SC GPU 이진 탐색 트리(Binary Search Tree)