[자료구조] Array / Linked List

Array

배열은 연속된 메모리 공간에 같은 타입을 갖는 데이터를 저장하는 자료구조이다.

동일한 타입의 여러 데이터를 연속된 공간에 저장하게 되면 각각의 요소의 위치를 시작 위치에 오프셋을 더하는것 만으로 구할 수 있다.

 

데이터 접근

배열은 특정 순서의 데이터에 접근할 때, 해당 순서의 인덱스를 통해 바로 접근이 가능하다.

 

데이터 삽입, 삭제

특정 인덱스에 데이터를 삽입하거나 해당 데이터를 삭제할 때, 배열은 아래와 같은 과정이 이루어진다.

데이터 삽입

데이터 삭제

삽입 혹은 삭제하려는 위치의 뒤에 있는 모든 요소들에 대한 작업이 필요하다.

 

Linked List

링크드 리스트는 연속되지 않은 메모리 공간에 데이터를 저장하는 선형 자료구조이다.

링크드 리스트의 데이터는 다음 데이터의 위치 혹은 이전 데이터의 위치를 나타내는 포인터로 각각 연결되어 있다.

데이터 필드와 참조 필드를 묶어 노드라 하고, 링크드 리스트는 이런 노드들로 이루어져 있다.

 

데이터 접근

링크드 리스트는 메모리가 연속되어 있는 구조가 아니기 때문에 특정 순서의 데이터에 접근하기 위해서는 처음 노드부터 해당 노드가 나올때까지 탐색해야 한다.

 

데이터 삽입, 삭제

링크드 리스트에 노드를 삽입하거나 삭제할 때, 링크드 리스트는 아래와 같은 과정이 이루어진다.

위와 같이 전, 후 노드가 참조하는 노드를 바꿔주면 노드를 삽입, 삭제할 수 있다.

 

Array / Linked List 비교

1. 데이터 접근

배열은 데이터에 접근하기 위해서 인덱스를 사용하므로 바로 접근할 수 있다.

링크드 리스트는 데이터에 접근하기 위해서 head부터 원하는 순서의 데이터에 접근할 때까지 탐색해야 한다.

2. 데이터 삽입, 삭제

배열은 데이터를 삽입 혹은 삭제하게 되면 뒤에 있는 나머지 원소들을 당기거나 미뤄줘야 한다.

연결 리스트는 참조 링크를 바꿔주기만 하면 되기 때문에 상대적으로 배열에 비해 빠르다.

3. 그 외

배열은 고정된 길이를 갖고, 연결 리스트의 경우에는 동적이고 유연한 사이즈를 갖는다.

메모리는 다음이나 이전 참조 링크를 갖는 연결 리스트에 비해 인덱스만 갖는 배열이 더 적게 요구된다.

그러나 메모리 사용율로 본다면 연결 리스트가 더 효율적이다.

왜냐하면 배열의 길이는 고정되어 있고 사용하지 않는 공간이 있을 수 있지만 연결 리스트의 경우에는 저장하는 데이터만큼의 공간만 사용하기 때문이다.

추가로 배열은 더 큰 공간이 필요한 경우 새로 선언하고 기존의 요소들을 다 옮겨주어야 한다.