20230309 [자료구조] 배열과 연결리스트

0. 자료구조

• 컴퓨터 과학에서 효율적인 접근 및 수정을 가능하게 하는 자료의 조직, 관리, 저장을 의미한다.
• 자료구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다.
• 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다.

1. 배열(Array)

• 가장 일반적인 구조이다. 메모리 상에 같은 타입의 자료가 연속적으로 저장된다. 자료값을 나타내는 가장 작은 단위가 자료를 다루는 단위이다.
• 컴퓨터 과학에서 배열은 번호(인덱스)와 번호에 대응하는 데이터들로 이루어진 자료 구조를 나타낸다.
• 일반적으로 배열에는 같은 종류의 데이터들이 순차적으로 저장되어, 값의 번호가 곧 배열의 시작점으로부터 값이 저장되어 있는 상대적인 위치가 된다.
• 대부분의 프로그래밍 언어에서 사용할 수 있는 가장 기초적인 자료 구조로, 기본적인 용도 외에 다른 복잡한 자료 구조들을 표현하기 위해서 또는 행렬, 벡터 등을 컴퓨터에서 표현하는 용도 등으로도 사용된다.

2. 연결 리스트 (Linked List)

• 노드를 단위로 한다. 노드는 자료와 다음 노드를 가리키는 참조값으로 구성되어 있다. 노드가 다음 노드로 아무것도 가리키지 않으면 리스트의 끝이다.
• 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다.
• 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.
• 연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. 그러나 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다.

언제 배열을 쓰고 언제 연결 리스트를 쓰면 좋을까?

• 배열 : 빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을 때
  (배열은 인덱스를 통한 빠른 접근이 가능하기 때문이다. + 배열은 삽입/삭제가 오래 걸리고 중간에 있는 데이터가 삭제되면 공간 낭비가 발생하기 때문이다. )
• 연결 리스트 : 삽입과 삭제 연산이 잦고, 검색 빈도가 적을 때 (연결 리스트는 삽입, 삭제에 용이하기 때문이다. + 연결 리스트는 임의 접근이 불가능하여, 처음부터 탐색을 진행해야 하기 때문이다. )