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

데이터 집합이 있을때 검색만 하면 된다고 생각한다면 검색에 사용할 알고리즘은 계산 시간이 가장 짧은것을 선택하면 된다. 그러나 데이터 집합에 대한 검색뿐아니라 데이터의 추가, 삭제 등을 자주하는 경우라면 검색 이외의 작업에 소요되는 비용을 종합적으로 평가하여 알고리즘을 선택해야 한다.

 

 

리스트는 포인터를 사용해 자료를 순차적으로 저장하는 선형 자료구조를 말한다. 실제로 배열과 리스트의 차이는 속도와 자료의 크기에서 나타난다.

• 배열은 기본적으로 인덱스로 자료를 찾기 때문에, 자료의 삽입, 삭제, 검색에서 리스트보다 무조건 빠르다. 하지만 고정된 데이터 크기 때문에 메모리의 낭비가 심하다는 단점이 있다.
• 리스트는 고정된 크기 없이 포인터로 자료들을 연결하기에, 자유자재로 데이터의 크기를 바꿀 수 있다. 하지만 인덱스가 없으므로 배열보다 자료를 찾는데 더 오랜시간이 걸려 배열보다 느리다는 단점이 있다.

따라서 상황에 맞게 리스트를 쓸 것인지 배열을 쓸 것인지 판단해야 한다. 리스트의 개념에 대해 알았으니 이제 리스트의 종류에 대해 알아보려 한다. 리스트는 구현에 따라 크게 연결 리스트 (Linked List)와 배열 리스트 (Array List)로 나뉘게 된다.

 

시작하기에 앞서...

 

사실 리스트는 빠른 성능을 내야하는 알고리즘 문제에 그렇게 적합한 자료형은 아닐 뿐더러 자주 출제되는 유형도 아니다. 심지어 자바나 C++에서는 이미 기본 라이브러리로 구현이 되어 있어 import해서 사용하기만 하면 된다. 그럼에도 불구하고 리스트를 공부해야 하는 이유는 리스트 구현에 사용된 알고리즘이 스택이나 큐부터 시작해 트리, 그래프까지, 모든 자료구조의 구현에 사용되기 때문이다. 따라서 심화까지는 아니더라도 리스트의 구현 방법과 배열과의 차이 정도는 짚어두고 넘어가자!

 

1. 연결 리스트 (Linked List)

 

1) 개념

우리가 기본적으로 언급하는 리스트는 대부분 연결 리스트를 지칭한다. 연결리스트는 다음과 같이 노드와 링크를 통해 자료를 연결한다.

 

노드는 data와 link로 이루어져 있으며, data에는 자료의 정보가, link에는 다음 노트를 가리키는 포인터가 저장된다. 리스트의 시작은 head이며, link를 통해 검색하는 노드가 나올 때까지 다음 노드로 이동한다. 연결리스트에서 기본적으로 사용되는 함수는 다음과 같다.

node* init_node(int data); // 노드 생성 void insert_node(node** head, int idx, int data); // idx 위치에 노드 삽입 void delete_node(node** head, int idx); // idx 위치의 노드 삭제 void print_node(node* head); // 전체 리스트 출력

node* init_node(int data); // 노드 생성 
void insert_node(node** head, int idx, int data); // idx 위치에 노드 삽입 
void delete_node(node** head, int idx); // idx 위치의 노드 삭제 
void print_node(node* head); // 전체 리스트 출력

여기서 가장 중요한 함수는 insert와 delete인데, 각각의 논리는 다음과 같다.

 

- insert

- delete

 

2) 구현

포인터와 반복문을 이용해 리스트에서도 idx라는 인덱스 값으로 데이터에 접근이 가능하게 구현할 수 있다.

(원본블로그 참고)

 

 

2. 동적 배열 (Dynamic Array)

 

1) 개념

동적 배열은 배열과 연결 리스트의 단점을 어느정도 보완한 자료형으로, 기본적으로 배열로 구현되기에 초기에 고정된 크기를 할당받으며 배열과 거의 비슷한 속도를 나타내지만, 필요에 따라 동적으로 크기가 변화하는 특징을 갖는다.

 

하지만 실제로 동적 배열은 직접 구현할 일이 거의 없다. 이미 C++의 vector나 자바의 ArrayList 등의 기본 라이브러리로 구현되어 있기 때문에 우리는 이를 가져다 쓰기만 하면 된다.

 

 

출처:

1. 자료구조와 함께배우는 알고리즘 입문 - 이지스퍼블리싱

2. https://cupjoo.tistory.com/44