자료구조: 배열(Array)와 리스트(List)

1. 배열 (Array)

배열은 Static array, Fixed array로 불리기도 합니다.

• 정적 배열이라고 말할 수 있으며, input 값의 개수가 정해져 있는 자료구조입니다.
  • 이 때, input에 정해진 수 이상 들어올 경우 Error을 발생시킵니다.
  • 선언을 통해 미리 메모리를 할당해서 메모리에 비해 적은 양의 데이터가 들어오더라도 유동적으로 그 크기를 줄일 수 없습니다. (메모리 낭비)
• index가 value의 고유한 식별자라고 볼 수 있기 때문에 인덱싱(indexing)에 강점을 보입니다.

 

2. 리스트 (List)

Array와 다르게 리스트는 Dynamic Array로 불립니다.

• 동적 배열이라고 말할 수 있으며, input 값이 들어올 때마다 동적으로 메모리를 할당하는 자료구조입니다.

  • 사용자 입장에서는 편하지만, 후술할 Singly Linked List와 같이 링크가 하나 사용되는 경우 노드당 4byte, Doubly Linked List의 경우 8byte가 추가로 필요하기 때문에 경우에 따라 효율적으로 사용해야 합니다.

• 리스트 종류에 따라 인덱싱(indexing)에 배열보다는 떨어지는 퍼포먼스를 보일 때가 있습니다.

노드(Node)의 구조

리스트는 input을 받을 때마다 노드의 형태로 이 값을 저장하는데, 노드는 크게 데이터 필드(Data Field), 링크(Link)로 이루어져 있습니다.

• 노드의 테일(tail)을 다음 노드의 헤드(head)에 잇는 방식으로 리스트가 구성됩니다.

리스트의 종류

1. 단일 연결 리스트 (Singly Linked List)

노드가 한 방향으로 이어진 리스트를 말합니다. 한 번 다음 index에 넘어가면 다시 돌아올 수 없습니다. (다시 처음부터 시작해야 함)

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

노드가 양방향으로 이어진 리스트를 말합니다.

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

노드는 한 방향으로 이어졌지만, 마지막 노드가 가리키는 index가 처음 노드로 순환하는 형태의 리스트를 말합니다. CPU의 라운드 로빈 알고리즘 등에 유용하게 사용되지만, 무한 순환을 조심해야 합니다.

 

3. 배열과 리스트의 비교

처음에 설명한 메모리 할당의 차이도 있지만, 요소를 추가/삭제할 때에도 배열과 리스트의 차이가 존재합니다.

요소 (element) 추가

• 배열에서 특정 index에 값을 추가할 경우, 그 index에 들어 있던 값이 갱신됩니다. 반면 리스트에서 똑같은 과정을 거칠 경우 그 index에 노드가 추가되며, 기존에 그 index부터 이후에 있던 값들이 자동으로 한 칸씩 밀려납니다.

요소 (element) 삭제

• 배열에서 특정 index의 값을 삭제할 경우, 그 index의 들어 있던 값이 사라지지만 index는 그대로 남아 있습니다. 반면 리스트에서 같은 과정을 거칠 경우 그 노드 전후의 노드들의 헤드와 테일이 가리키는 방향을 조정하여 노드를 완전히 삭제할 수 있습니다.

	배열 (Array)	리스트 (List)
메모리 할당 효율		O
인풋 하나당 메모리	O
중간 요소 추가/삭제		O

• 여기서 메모리 할당 효율은 인풋 개수를 모를 때 기준입니다.

 

4. 언어별 배열 / 리스트 구조

제가 사용하는 언어를 위주로 작성하였습니다.

• C: 배열([])은 존재하지만, 리스트는 따로 노드와 Linked list로 구현해야 합니다.
• Java: 배열과 리스트 모두 클래스가 따로 구현되어 있습니다. (Array, ArrayList와 LinkedList)
• Python: 리스트만 구현이 되어 있지만, 배열과 리스트를 구분하지 않아도 사용할 수 있게 다양한 기능을 가집니다.