Array란 ?
값의 Collection들을 저장할 수 있는 primitive type의 자료구조이다.
배열은 다음에 올 블록에 값들이 저장된다.(continous data structure)
Complexity Of Array
검색(postion)
constant time
각 블록사이즈도 같고, 순차적으로 저장되어 있기 때문에 한번에 특정 블록에 접근할 수 없다.
할당
constant time
할당할 블록의 index값을 알고 있고, 바로 가서 재할당해주면 된다.
삽입
linear time
삽입을 위해서는 삽입하기 위한 자리가 필요하다. 종속되는 값들을 모두 이동시켜야 한다.
삭제
linear time
삭제의 경우도 마찬가지이다. 삭제하고나면 종속되는 값들을 모두 이동시켜야 한다.
검색(value)
linear time
순차적으로 블록의 값을 검색해야한다.
LinkedList란?
배열과의 큰 차이점은 '어떻게 저장하는지' 이다.
연결리스트의 경우 비연속적인 자료구조이다.
메모리에 순차적으로 저장되기 보다 전반적으로 걸쳐 저장된다.
각 값들은 노드라 불리는 연결리스트 안의 작은 자료구조 안에 저장된다.
노드는 값과 다음 노드의 참조를 포함한다.
연결리스트는 그들의 첫 번째 값과 마지막 값을 계속해서 참고한다. 이 참조를 head와 tail이라 부른다.
Complexity of LinkedList
검색
linear time
연결리스트는 연속적으로 저장되어 있지 않기 때문에 array처럼 constant time을 갖지 않는다.
head의 프로퍼티는 리스트들의 첫 번째 노드를 계속해서 참조하고있다.
각 노드들은 리스트의 다음 노드를 가르키는 포인터를 포함하고있다.
다음 노드의 참조를 따라서 계속 이동한다. 최악의 경우, 리스트의 끝까지 도착해야 할 수도 있다.
할당/검색(value)
linear time
삽입
constant time
-
마지막에 삽입할 경우
새로 값을 넣고 tail 노드의 다음 포인터가 새로운 값을 참조하도록 한 뒤에, tail의 참조값이 새로운 값을 참조하게 한다. -
중간에 삽입할 경우
우선 삽입할 위치를 찾은 후에 새로운 값을 만든다. 그러고 원래의 노드가 다음 참조를 하도록 만든다.
검색이 포함됬기 때문에 linear타임이라 생각할 것이지만,
삽입이 일어날 때 이미 참조를 하고 있기 때문에 constant time이다.
공간을 만들기 위해 종속적인 값들을 이동시킬 필요도 없고, 삽입 위치에서 참조를 갖는 한, 유한한 단계로 노드들을 추가할 수 있다.
삭제
처음 값을 삭제할 경우
head의 참조값을 원래 값에서 다음 값으로 변경한다.
-> constant time
중간 값을 삭제할 경우
- 참조값을 바꿔줘야 하는 노드를 찾는다.
- 앞으로 진행될 노드 또한 찾아줘야한다.
=> linear time
이런 제한은 노드의 구조(가치, 다음참조)에 의해 부과된다.
이런 제한을 없애기 위해 노드를 변경한다면?
=> doubly linked list
Doubly-Linked Lists
각 노드들은 값과 두가지 노드에 대한 참조(이전 노드와 다음 노드)를 갖는다.
이 변화는 삽입, 조회, 검색, 할당에는 영향을 미치지 않지만 삭제에는 영향을 미친다.
삭제
이전 값에 대한 포인터가 어떤 영향을 미칠까?
변경할 노드가 진행될 노드의 참조값을 포함하고 있기 때문에, 더이상 앞으로 진행될 노드를 찾아줄 필요가 없다.
약간의 참조값을 바꿔주면 된다.
이런 변화가 어떤 위치에서든 삭제 연산을 constant time으로 만들어준다.
Array/Linked List/Doubly-Linked Lists
-
Array
lookup - constant
insert, removal - linear -
Linked List
insert - constant
lookup, removal - linear -
Doubly-Linked List
insert, removal - constant
*each node takes up a little more space
