Array & LinkedList

자료 구조

데이터를 효율적으로 저장, 관리, 처리하기 위해 컴퓨터에 데이터를 조직화하고 관리하는 방법으로 다양한 종류의 자료 구조가 있으며, 각각은 특정 종류의 문제를 해결하기 위해 설계되었다.

 

기본적인 자료 구조에는 배열, 연결 리스트, 스택, 큐, 트리, 해시 테이블 등이 있다.

 

배열(Array)

• 배열은 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조이다.
• 메모리 상에서 연속적으로 저장되어 있는 특징을 갖기 때문에 index를 통한 접근이 용이하다.
• 고정된 크기를 가지며, 크기 변경이 어렵다, 미리 할당된 메모리 크기를 초과하면 새로운 메모리 공간을 할당하고 데이터를 복사해야 한다.
• 메모리 사용이 효율적으로 추가적인 메모리를 사용하지 않는다.

시간 복잡도

• 탐색 : O(1). 단, 접근하려는 인덱스를 알고 있어야 한다. 순차적으로 탐색 시에는 O(n).
• 삽입 / 삭제 :
  • 배열의 처음 또는 중간에 삽입 및 삭제 : O(n) - 삽입 지점 이후의 데이터를 옮겨야 하기 때문
  • 배열의 끝에 삽입 및 삭제 : O(1)

 

연결 리스트(Linked List)

• 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료 구조이며, 첫 번째 노드를 head, 마지막 노드를 tail이라고 한다.
• 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다.
• 크기 변경이 쉽다, 새 노드를 동적으로 할당하거나 제거함으로써 리스트의 크기를 변경할 수 있다.
• 배열과는 다르게 메모리를 연속적으로 사용하지 않는다.
• 배열과는 다르게 순차적으로 접근해야 하는 면에서 불리할 수도 있으나, 노드가 연괼된 구조이기 때문에 삽입, 삭제에 용이하다.
• 메모리 사용이 비효율적일 수 있다, 각 노드는 데이터와 포인터를 저장해야 해서 추가적인 메모리를 사용한다.
• Tree 구조의 근간이 되는 자료 구조이며, Tree에서 사용되었을 때 그 유용성이 드러난다.

시간 복잡도

• 탐색 : O(n)
• 삽입 / 삭제 : 삽입과 삭제 자체는 O(1)이다.
  • 연결 리스트의 처음에 삽입/삭제 : O(1)
  • 연결 리스트의 중간에 삽입/삭제 : O(n) - 탐색 시간 소요
  • 연결 리스트의 끝에 삽입/삭제 :
    • 끝을 가리키는 별도의 포인터를 갖는 경우 : O(1)
    • 끝을 가리키는 별도의 포인터를 갖지 않는 경우 : O(n) - 탐색시간 소요

 

배열과 연결 리스트 비교

장점

• 배열 : 인덱스를 통한 빠른 접근 가능
• 연결 리스트 : 삽입 / 삭제 용이

단점

• 배열 :
  • 삽입/삭제가 오래 걸림
  • 배열 중간에 있는 데이터가 삭제되면, 공간 낭비가 발생함
• 연결 리스트 : 임의 접근이 불가능하여, 처음부터 탐색을 진행해야 함

용도

• 배열 : 빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을 때
• 연결 리스트 : 삽입과 삭제 연산이 잦고, 검색 빈도가 적을 때

 

연결 리스트 종류

이중 연결 리스트(Doubly Linked List)

• 연결 리스트와 다르게 전/후로 탐색이 가능한 구조
• 단순 연결 리스트의 노드는 데이터와 다음 노드의 주소를 저장하지만, 이중 연결 리스트의 노드는 데이터, 이전 노드의 주소와 다음 노드의 주소를 저장하게 된다.
• 장점 : 단순 연결 리스트에서는 최악의 경우 n 번의 탐색을 해야하지만, 이중 연결 리스트는 얻고자 하는 데이터의 위치가 tail에 가깝다면 tail에서부터 역방향으로 탐색이 가능하기 때문에 탐색 시간을 줄일 수 있다.

\

 

원형 연결 리스트(Circular Linked List)

• 원형 연결 리스트는 단순 연결 리스트의 마지막 노드가 null을 가리키는 게 아닌, 처음 노드를 가리키는 구조이다.
• head에서부터 순회를 반복적으로 진행하다보면 다시 처음으로 돌아오는 구조이다.
• 이중 연결 리스트도 마지막 노드가 처음 노드를 가리키는 구조가 되면, 이를 이중 원형 연결 리스트라고 한다.

원형 연결 리스트

이중 원형 연결 리스트