[알고리즘, 자료구조] 배열과 연결리스트

배열 (Array)

배열은 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리위치에 있는 데이터를 모아놓은 집합이다. 또한 중복을 허용하고 순서가 있다. 탐색에 O(1)이 되어 랜덤 접근이 가능하며 삽입과 삭제는 O(n)이 걸린다.

랜덤접근 : 임의의 인덱스에 해당하는 데이터 접근 방식이며 시간 복잡도는 O(1)이다.

순차적접근 : 데이터를 저장된 순서대로 검색하는 접근 방식이며 시간 복잡도는 O(n)이다.

---

연결리스트 (Linked list)

연결리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화 시킨 자료구조 이다. 삽입과 삭제가 O(1)이 걸리며 탐색에는 O(n)이 걸린다.

 

https://yjg-lab.tistory.com/118

• 단일연결리스트 : 단순히 한쪽 방향으로만 연결된 단방향 연결리스트로 자료 생성시 노드가 생성되고 포인터는 생성된 노드를 가리킨다. 장점으로 자료 추가 및 삭제 시 O(1)의 시간복잡도를 가지고 단점으로는 배열이나 트리구조와는 달리 특정 위치 검색시 O(n)의 시간복잡도를 갖는다.

 

• 이중연결리스트 : 양쪽 방향으로 연결된 쌍방향 리스트로 자료 생성시 노드가 생성되고 전 노드의 포인터는 생성된 포인터를 가리킨다. 생성된 노드의 Prev 포인터는 전 노드를 가리킨다. 장점으로 양방향으로 이동할 수 있어 데이터를 삭제할 때 이전 노드를 찾기위해 한번 더 탐색하지 않아도 되서 빠르고 단점으로는 메모리를 더 사용한다. 단일 연결리스트에 비해 약간 더 복잡하다.
  • 참고 : https://www.youtube.com/watch?v=SCdd9SzOk9Q

 

• 환형 연결리스트 : 고리의 처음과 끝이 함께 연결되어 있는 연결 리스트로 양방향과 같지만 마지막 노드의 Next 포인터는 처음을 가리킨다.

---

배열과 연결리스트 비교

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

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

따라서 탐색은 배열이 빠르고 연결리스트가 느리다. 또한 데이터 추가 및 삭제는 연결리스트가 빠르고 배열이 느리다.

	배열	연결리스트
탐색	빠름	느림
추가	느림	빠름
삭제	느림	빠름

 

 

보면 좋은 자료

https://www.youtube.com/watch?v=sq49IpxBl2k