[개념 콕] 배열과 연결 리스트

배열 (Array)

배열이란?

배열의 특징

• 정적 자료구조
배열은 크기를 미리 정해놓아야 하며, 해당 크기 만큼의 연속된 메모리 주소를 할당 받습니다.

• 연속된 메모리 주소
배열의 요소들은 메모리 상에 연속적으로 저장됩니다. 이러한 특성 때문에 배열의 요소에 빠르게 접근할 수 있습니다.

• 활용
• 정보를 저장할 때 사용합니다.

• 인덱스(index)
• 배열의 각 요소는 인덱스를 통해 접근합니다.
• 인덱스는 0부터 시작하며, array[0]와 같이 대괄호 안에 인덱스를 명시(배열 이름 [인덱스 값])하여 해당 위치의 요소에 접근할 수 있습니다.

• 장점
• 인덱스를 통해 임의의 요소에 빠르게 접근할 수 있습니다.
• 특정 인덱스의 요소에 접근하는 시간 복잡도는 O(1)입니다.

• 단점
• 배열의 크기는 고정되어 있으므로, 배열의 크기보다 더 많은 데이터를 저장할 수 없습니다.
• 배열 중간에 요소를 삽입하거나 삭제하는 경우에는 다른 요소들을 이동시켜야 하므로 O(n)의 시간 복잡도가 소요됩니다.
• 중간에 요소를 삽입하거나 삭제하는 경우, O(n)의 시간 복잡도가 소요됩니다.

• 정적 자료구조 → 도서관 책장 칸의 개수가 미리 정해져 있는 것처럼, 배열의 크기가 미리 지정되어야 합니다.

• 연속된 메모리 주소 → 책장에 책을 일렬로 나열해 놓는 것처럼, 배열의 요소들이 메모리 상에 연속적으로 저장됩니다.

• 인덱스 → 책장의 각 칸에 번호가 매겨져 있는 것은 배열의 인덱스와 같은 개념입니다. 첫 번째 칸은 0번, 두 번째 칸은 1번 등으로 번호가 붙어 있어 책을 찾을 때 해당 번호를 사용할 수 있습니다.다.

• 장점 → 장의 번호를 알고 있다면 해당 책을 바로 찾을 수 있는 것처럼, 배열에서도 인덱스를 통해 특정 요소에 빠르게 접근할 수 있습니다.

• 단점 → 책장이 꽉 차면 더 이상 책을 넣을 수 없는 것처럼, 배열도 미리 지정된 크기 이상으로 요소를 저장할 수 없습니다. 또한 책장 중간에 책을 넣거나 빼려면 다른 책들을 옮겨야 하는 것처럼, 배열에서도 중간에 요소를 삽입하거나 삭제하려면 다른 요소들을 이동시켜야 합니다.

연결 리스트 (Linked List)

연결 리스트란?

연결 리스트의 특징

• 동적 자료구조: 크기를 미리 지정할 필요가 없습니다. 필요에 따라 메모리를 할당받아 데이터를 저장할 수 있으며, 연속된 메모리 공간을 요구하지 않습니다.

• 노드(Node):
• 연결 리스트는 노드라는 단위로 구성됩니다.
• 각 노드는 데이터를 저장하는 부분과 다음 노드의 주소를 가리키는 포인터로 이루어져 있습니다. 이를 통해 노드들이 연결되어 있는 구조를 만듭니다.

• 활용
• 크기를 유동적으로 관리해야 할 때, 또는 데이터 추가 및 삭제가 빈번할 때 유용합니다.

• 장점
• 크기의 제한이 없으므로 필요에 따라 데이터를 추가하거나 삭제할 수 있습니다.
• 특히 맨 앞이나 맨 뒤에 노드를 삽입하거나 삭제하는 경우에는 O(1)의 시간 복잡도로 빠르게 처리할 수 있습니다.

• 단점
• 배열과 달리 인덱스를 통한 임의 접근이 불가능합니다.
• 특정 위치의 데이터에 접근하기 위해서는 처음부터 순차적으로 탐색해야 하므로 배열에 비해 탐색 속도가 느립니다. 즉, O(n)의 시간 복잡도가 소요됩니다.

• 동적 자료구조 → 목걸이에 구슬을 추가하거나 제거할 수 있는 것처럼, 연결 리스트의 크기는 미리 정해져 있지 않고 필요에 따라 동적으로 변경될 수 있습니다.

• 노드 → 목걸이의 각 구슬은 데이터를 담고 있으며, 연결되어 있습니다.

• 장점 → 목걸이에 구슬을 추가하거나 제거하는 것이 쉬운 것처럼, 연결 리스트에서도 노드를 추가하거나 삭제하는 것이 간단합니다. 새로운 노드를 추가할 때는 포인터만 변경하면 됩니다.

• 단점 → 목걸이에서 특정 구슬을 찾기 위해서는 처음부터 순서대로 찾아야 하는 것처럼, 연결 리스트에서도 특정 노드에 접근하기 위해서는 순차적으로 탐색해야 하므로 접근 속도가 느립니다.

배열과 연결 리스트의 차이점

내일배움캠프는 개발에 필요한 핵심만 배웁니다