배열(Array)과 연결리스트(List)

배열 ( Array )

📝 연속된 메모리 공간에 요소들을 저장하는 자료구조이다.

 

 

👍 장점

• 연속된 데이터 공간을 사용하고 있기 때문에 각 칸의 크기와 요소의 인덱스를 알고 있을 때 임의 접근이 가능하여 고정 시간을 가진다.

👎 단점

• 배열의 새로운 요소를 추가하거나 삭제할 때 해 연속된 모든 요소의 위치를 옮겨야 하기 때문에 추가•삭제가 힘들다.
  • 배열을 미리 생성해 두는 방법도 있지만 이런 경우 사용하지 않는 메모리 공간이 발생할 수 있어 메모리 누수가 생길 수 있다.

 

 

 

연결 리스트

📝 각 원소들을 메모리 주소로 연결해 저장하는 자료구조이다.

 

 

👍 장점

• 각 원소를 주소 값을 참조하는 방식으로 연결 해두었기 때문에 원소를 추가하거나 삭제할 때 가리키고 있는 주소값을 변경하거나 추가로 가리키게 하면 되기 때문에 배열에 비해 원소 추가 삭제가 쉽다.

👎 단점

• 원소의 위치를 탐색하기 위해 첫번째 원소 부터 하나씩 타고 들어가는 순차 접근만 가능 하기 때문에 선형 시간을 가져 상대적으로 느리다.

 

 

배열과 연결 리스트 비교

	배열	연결 리스트
읽기(Read)	O(1)	O(n)
삽입(Insert)	O(n)	O(1)
삭제(Delete)	O(n)	O(1)

 

📝 고정 시간과 선형 시간

📌 고정 시간 
빅오 표기법으로 O(상수) 와 같이 자료의 길이와 상관 없이 탐색 속도가 일정한 경우를 뜻한다.
 
📈 선형 시간
빅-오 표기법으로 O(N)을 의미한다. 자료의 길이에 비례하는 시간이 필요한 경우를 뜻한다.

 

📝 자료 접근 방법

 🎰 임의 접근 (random access)
순서가 있는 자료에 접근하기 위해 자료를 건너 뛸 수 있는 방식을 의미한다.

 🚂 순차 접근 ( sequential access )
원소를 첫 번째 부터 하나씩 읽는 것을 의미한다.