[자료구조 문제] 2.퀴즈로 연결 리스트 정리하기

[자료구조 문제] 2.퀴즈로 연결 리스트 정리하기

 

다음 빈칸에 들어갈 알맞은 말을 넣어보세요.

 

1.배열의 OO을 보완해서 나온 데이터 구조가 연결리스트 자료구조입니다.

 

2.배열에서 임의의 위치에 요소를 삽입하거나, 임의의 위치에서 요소를 삭제하는 작업은 해당 위치 뒤에 있는 요소들을 하나씩 뒤칸 혹은 앞칸으로 옮겨야 하기 때문에 OO이 오래 소요됩니다.

 

3.이런 문제를 해결하기 위해 고안된 자료구조가 OOOOO(linked list)입니다. OOOOO는 특정 위치에 요소의 삽입과 삭제를 배열보다 빠른 시간에 처리할 수 있습니다.

 

4.연결 리스트의 특징은 데이터와 OOO가 한 쌍으로 구성되어 있다는 점입니다. 일반적으로 데이터와 OOO를 노드(node)라고 부릅니다.

 

5.연결 리스트는 노드(node)들이 메모리상에 OO해서 저장되지 않습니다. 또한 배열과 다르게 메모리상의 공간을 미리 예약할 필요없이 언제든 동적으로 메모리 공간을 생성할 수 있습니다.

 

6.배열은 요소들이 OOO의 연속된 공간에 저장되어 있다면, 연결 리스트는 노드(node)들이 OOO 여러 공간에 흩어져 있습니다.

연결 리스트는 노드의 논리적 OO와 메모리의 물리적 OO가 동일하지 않습니다.

 

7.각 노드(node)들이 이전 노드(node)와 다음 노드(node)를 가리키는 포인터를 가지고 있는 연결 리스트를 OOO 연결 리스트라고 합니다.

 

8.각 노드(node)가 다음 노드(node)를 가리키는 포인터만 가지는 연결 리스트를 OOO 연결 리스트라고 합니다.

 

9.노드(node)는 C언어에서 Struct 데이터 타입으로 구현할 수 있습니다. 노드(node)의 OOO 필드는 연결 리스트의 값(Value)을 저장하기 위한 부분으로 필요에 따라 여러 필드로 이루어질 수 있습니다. 즉 OOO 필드에는 여러 종류의 값(Value)이 저장될 수 있습니다.

 

10.노드(node)의 OOO 필드는 연결 리스트에서 다음 노드(node)가 저장되어 있는 메모리 주소를 저장합니다. 이 주소를 이용하여 다음 노드(node)를 찾습니다. 

 

11.연결 리스트는 첫 번째 노드(node)와 마지막 노드(node)에 대한 포인터를 가지고 있습니다. 이 포인터들을 각각 OO(head)와 꼬리(tail)라고 부릅니다. 대부분 연결 리스트는 이와 같이 OO와 꼬리에 대한 포인터 변수만을 가진 구조체나 클래스로 구현됩니다.

 

12.연결 리스트의 머리(head) 포인터 변수는 연결 리스트의 시작 노드(node) 즉, 연결 리스트의 O번째 노드(node)를 가리킵니다.

 

13.마지막 노드(node)의 포인터는 더 이상 가리킬 노드(node)가 없기 때문에 OOOO 포인터로 표현합니다.

 

14.배열과 다르게 연결 리스트에서는 메모리 여러 공간에 노드(node)들이 흩어져 있기 때문에 특정 위치의 값(node)을 찾기가 쉽지 않습니다. n번째 노드(node)를 찾기 위해서 연결 리스트의 머리(head)부터 하나씩 OOO를 따라가며 다음 노드(node)를 찾아야 되기 때문입니다.

 

15.연결 리스트에서 노드(node)들의 순서는 포인터에 의해 정의되기 때문에 노드(node)들의 순서를 유지하면서 새 노드(node)를 OO하거나 기존 노드(node)를 삭제하는 작업은 아주 간단합니다.  

 

16.연결 리스트에서 노드(node)를 삽입 또는 삭제 할때 다른 노드(node)들은 그대로 두고 삽입, 삭제할 노드(node)와 해당 노드(node) 이전과 이후 노드(node)의 포인터만 바꾸면 됩니다. 따라서 연결 리스트에서의 삽입과 삭제 속도는 OO 보다 빠릅니다.

 

 

목차

자료구조문제 1.퀴즈로 배열 정리하기

 

 

 

출처: '코딩퀴즈' 앱

 

문제 정답 확인

코딩퀴즈 안드로이드

https://play.google.com/store/apps/details?id=com.codingquiz.myapplication

 

코딩퀴즈 ios

https://apps.apple.com/kr/app/%EC%BD%94%EB%94%A9-%ED%80%B4%EC%A6%88/id1625309702