[자료구조] Array(배열) vs Linked List(연결리스트) ( + List)

Array

 가장 기본적인 자료구조인 Array 자료구조는, 논리적 저장 순서와 물리적 저장 순서가 일치한다. 따라서 인덱스(index)로 해당 원소(element)에 접근할 수 있다. 그렇기 때문에 찾고자 하는 원소의 인덱스 값을 알고 있으면 Big-O(1)에 해당 원소로 접근할 수 있다. 즉 random access 가 가능하다는 장점이 있는 것이다.

 

하지만 삭제 또는 삽입의 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤(O(1)), 또 한 가지의 작업을 추가적으로 해줘야 하기 때문에, 시간이 더 걸린다. 만약 배열의 원소 중 어느 원소를 삭제했다고 했을 때, 배열의 연속적인 특징이 깨지게 된다. 즉 빈 공간이 생기는 것이다. 따라서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift해줘야 하는 비용(cost)이 발생하고 이 경우의 시간 복잡도는 O(n)가 된다. 그렇기 때문에 Array 자료구조에서 삭제 기능에 대한 time complexity 의 worst case 는 O(n)이 된다.

삽입의 경우도 마찬가지이다. 만약 첫번째 자리에 새로운 원소를 추가하고자 한다면 모든 원소들의 인덱스를 1 씩 shift 해줘야 하므로 이 경우도 O(n)의 시간을 요구하게 된다.

 

하지만 자바스크립트의 배열의 경우 일반적인 의미의 배열과는 다르다.

 

이게 무슨말인가?

 

앞서말한것 처럼 하나의 타입으로 통일되어 있으며 서로 연속적으로 인접해 있는 배열을 밀집 배열(dense array)라 한다

 

자바스크립트는 배열의 요소를 위한 각각의 메모리 공간은 동일한 크기를 갖지 않아도 되며 연속적으로 이어져 있지 않은 희소 배열(sparse array) 이다. 이 말은 자바스크립트의 배열은 엄밀히 말해 일반적 의미의 배열이 아니며, 배열의 동작을 흉내낸 특수한 객체이다.

 

자바스크립트 배열은 인덱스를 프로퍼티 키로 갖으며 length 프로퍼티를 갖는 특수한 객체이다. 자바스크립트에서 사용할 수 있는 모든 값은 객체의 프로퍼티 값이 될 수 있으므로 어떤 타입의 값이라도 배열의 요소가 될 수 있다.

 

 

 

List

• 인덱스를 갖지만, 몇번째 데이터인지 정도를 의미
• 메모리 주소가 연속적이 아닐 수도 있음
• 포인터를 통해 다음 데이터의 위치를 가리키고 있어 삽입, 삭제가 쉬움
• 동적이므로, 배열과 다르게 크기가 정해져 있지 X

컴퓨터 공학에서의 list의 의미와 파이썬에서는 list의 의미는 다르다

파이썬의 list는 배열처럼 구현되어 있다.

파이썬 리스트의 아이템들은 메모리 상의 연속적인 위치에 배치되어, 인덱스처럼 사용이 가능하다.

 

Linked List

연결리스트의 노드는 논리적 저장순서와 물리적 저장순서가 다르다. 배열이 인덱스를 통해 원소에 접근한다면, 연결리스트는 포인터를 이용해 원소에 접근하다. 이 때 처음부터 끝까지 순차적으로 탐색하여 원소를 찾기 때문에 배열보다 접근 속도가 느릴 수 있다. 이 때 최악의 경우 모든 원소를 탐색할 수도 있으므로 탐색은 O(n) 의 시간이 걸린다.삽입/삭제 시에는 노드의 포인터만 재설정 해주면 되므로 그 속도가 배열보다 빠를 수 있다. 그러나 삽입/삭제를 할 위치를 찾기 위해 탐색이 필요해 여전히 시간은 O(n) 이 걸린다.

• Node : 데이터와 다음 데이터를 가리키는 주소(포인터)로 이루어져 있다.
• Pointer : 각 노드에서 다음 데이터를 가리키는 주소값을 가진다.
• Head : 링크드리스트에서 가장 시작점인 데이터를 의미한다.
• Tail : 링크드리스트에서 가장 마지막 데이터를 의미
• Next=None(또는 Null) : 다음 데이터가 없을 경우 포인터의 주소값은 None(또는 Null)이다.

파이썬에서는 Node를 구현하기 위해 Class를 사용해야 한다.