배열과 연결리스트

배열 (Array)

배열

• 다수의 데이터를 저장할 수 있는 자료구조
• 정적 타입의 언어에서는 한가지 타입의 자료만 저장할 수 있다. (C언어)
• 동적 타입의 언어에서는 여러가지 다른 타입의 자료가 저장 될 수 있다. (자바스크립트, 파이썬)
• 컴파일언어에서는 배열의 크기가 정적이기 때문에 한번 생성하면 바꿀수 없다.
• JS, Python 같은 스크립트 언어에서는 배열의 크기가 동적으로 조절 될 수 있다.
• bracket([])을 통해서 자료에 접근할 수 있다.

const array = [0, 1, 2];
console.log(array[2]) // 2

• 특정 데이터에 접근하는 것은 O(1)의 시간복잡도가 요구된다. 중괄호를 이용해서 해당 인덱스에 바로 접근할 수 있기 때문이다.
• 데이터를 검색(조회)하는 데에는 최대 배열의 크기 N 만큼을 찾아야한다. O(N)의 시간 복잡도.
• 메모리 상에 배열은 연속적으로 저장이 된다.
• 데이터를 추가 및 삭제하는 것은 데이터를 추가 / 삭제한 위치 이후의 데이터를 모두 한칸씩 뒤로 보내거나 앞으로 당겨야하기 때문에 추가 및 삭제가 자주 일어나는 구조에는 부적합하다.
• 데이터에 빠른 접근이 요구되는 구조에 적합하다.

 

연결리스트 (Linked List)

연결리스트

• 다수의 데이터가 연결 된 구조
• 데이터가 힙영역에 동적으로 할당되고 연속적으로 저장되지 않는다. (배열과 달리 크기가 제한적이지 않다)
• 일반적으로 리스트에서는 데이터에 접근, 검색 하기위해서는 리스트의 앞에서부터 찾아들어가야하므로 최악의 경우 O(N)의 시간복잡도가 요구된다. (검색 및 접근 속도가 느리다)
• 데이터의 삽입은 원하는 위치의 삽입할 데이터가 삽입할 위치 뒷 부분을 가리키게 하고 앞의 연결은 삽입할 데이터를 가리키게 하는 방식으로 효율적인 삽입이 가능하다.
• 삭제도 마찬가지로 원하는 위치의 데이터의 앞의 연결을 끊고 그 뒷 데이터를 가리키게 한 후, 삭제할 데이터가 가리키는 다음 데이터와의 연결을 끊어준다. 
• 배열과 다르게 삽입, 삭제가 순회할 필요없이 연결을 생성하고 끊는 것만으로 가능하다.
• 빈번하게 삽입, 삭제가 일어나는 구조에 적합하다.

 

틀린 부분이 있다면 지적해주시고 이해 부탁드립니다!