선형 자료 구조(연결리스트, 배열)

선형 자료 구조란 요소가 일렬로 나열되어 있는 자료 구조를 말한다.

 

연결 리스트

연결 리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조이다. 

삽입과 삭제가 O(1)이 걸리며, 탐색에는 O(n)이 걸린다.

위 그림과 같이 prev 포인터와 next 포인터로 앞 뒤의 노드를 연결시킨 것이 연결 리스트이다. 

참고로, 맨 앞에 있는 노드를 head라 한다.

• 싱글 연결 리스트 : next 포인터만 가지며, 한쪽 방향으로만 이동이 가능하다. 
• 이중 연결 리스트 : next 포인터와 prev 포인터를 가지며, 양방향으로 이동이 가능하다.
• 원형 이중 연결 리스트 : 이중 연결리스트와 동일하지만, 마지막의 노드의 next 헤더가 head 노드를 가리킨다.

배열

배열은 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합이다. 

또, 중복을 허용하고 순서가 있다. (정적 배열)

탐색에 O(1)이 되어 랜덤 접근이 가능하다. 삽입과 삭제에는 O(n)이 걸린다.

 

따라서 데이터 추가와 삭제를 많이 하는 것은 연결 리스트, 탐색을 많이 하는 것은 배열을 이용하는 것이 좋다.

 

랜덤 접근과 순차적 접근

직접 접근이라고 하는 랜덤 접근은 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능이다. 

이는 데이터를 저장된 순서대로 검색해야 하는 순차적 접근과는 반대를 의미한다. 

 

배열과 연결 리스트 비교

배열과 연결리스트의 형태를 상자 안에 든 어떤 데이터들로 비유하자면, 

배열은 상자를 순서대로 나열한 데이터 구조이며 몇 번째 상자인지만 알면 해당 상자의 요소를 끄집어낼 수 있다.

연결리스트는 상자를 선으로 연결한 형태의 데이터 구조이며, 상자 안의 요소를 알기 위해서는 하나씩 상자 내부를 확인해봐야 한다는 점이 다르다. 

즉, 배열은 랜덤 접근(직접 접근)이 가능하지만, 연결리스트는 불가능하다.

 

탐색의 경우는 배열이 빠르지만, 삽입과 삭제는 연결리스트가 더 빠르다. 배열은 삽입이나 삭제를 하려면 모든 요소의 위치를 옮겨야 하지만, 연결 리스트는 선을 바꿔서 연결해주기만 하면 되기 때문이다.