연결리스트와 배열

선형 자료구조

선형 구조란 자료를 구성하는 원소들을 하나씩 순차적으로 나열시킨 형태

자료들간 앞, 뒤 관계가 1:1 관계로 되어있음

 

[ 배열 ]

배열은 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조
메모리 상에서 연속적으로 저장되어 있는 특징을 갖기 째문에 index를 통한 접근이 용이
배열의 크기는 처음 생성할 때 정하며 이후에는 변경할 수 없음

 

[ 연결 리스트 ]

 

일련의 원소를 배열처럼 순차적으로 저장하지만 원소들이 메모리상에 연속적으로 위치하는 않는 자료구조

즉, 논리적인 순서는 지켜지지만 물리적인 순서는 상관하지 않음

여러 개의 노드들이 순차적으로 연결된 형태를 갖으며 첫번재 노드를 head, 마지막 노드를 tail이라고 함

순자적으로 접근해야 하지만 노드가 연결된 구조기이 때문에 삽입, 삭제가 용이

연결 리스트의 종류에는 구현 방법에 따라 단순 연결리스트, 이중 연결리스트, 원형 연결리스트 등이 있음

 

이중 연결리스트

 

단순 연결리스트가 다음 노드로 갈수는 있지만 이전 노드로 갈 수 없는 점을 보완하여 양쪽 방향 모두의 노드를 연결한 리스트
이전 노드의 주소, 데이터, 다음 노드의 주소를 가지므로 단일 연결리스트에 비해 메모리를 2배 만큼 더 사용하게 됨
삭제를 할 경우 차례대로 따라가서 O(n)번을 거쳐야 되는 단순리스트와는 다르게 끝을 가리키는 포인터가 있어 O(1)으로 개선됨

 

원형 연결리스트

 

단순 연결리스트의 마지막 노드의 포인터가 NULL이 아닌 헤드를 가리키는 형태의 리스트따라서 리스트의 끝이 존재하지 않음(즉, tail이 head로 연결되는 연결리스트)

 

 

[ 배열과 연결 리스트 비교 ]

시간복잡도 

	탐색	삽입	삭제
배열	O(1)	O(n) / O(1) 처음또는 중간/끝에 삽입 (삽입 지점 이후의 데이터를 옮겨야 됨)	O(n) / O(1) 처음또는 중간/끝에 삭제 (삭제 지점 이후의 데이터를 옮겨야 됨)
연결리스트	O(n)	O(1)	O(1) / O(n) 끝을 가리기키는 포인터 유/무

 

장점

• 배열 : 인덱스를 통한 빠른 접근 가능
• 연결 리스트 : 삽입/삭제 용이

단점

• 배열
  • 삽입/삭제가 오래 걸림
  • 배열 중간에 있는 데이터가 삭제되면, 공간 낭비가 발생함
• 연결 리스트 : 임의 접근이 불가능하여, 처음부터 탐색을 진행해야 함

용도

• 배열 : 빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을 때
• 연결 리스트 : 삽입과 삭제 연산이 잦고, 검색 빈도가 적을 때