무냐의 개발일지
[Coursera] Data Structure _Week1 / Arrays & Lists 본문
1. Array
- 특징 : Contiguous area of memory, equal-size elements, Indexed by contiguous integers
(보통은 0에서 시작하지만, 이렇게 1에서 시작도 가능)
- 장점 : We have Constant time access to elements, either read or write. 언제든 특정 칸을 읽을수도, 쓸수도 있음 - address가 있음
EX) Address of the Element i ?
= array address + ( element_size * (i - first index))
= array address + 7*(4 - 1)
이렇게 하면 4번의 access 를 얻을 수 있다
Q)
A) 1000 + 8*(6-0) = 1048
| Multi-Dimemsional Array
skip the full rows we're not using & skip the columns we're not using
= array address + element size * [((row index - 1) * element size) + (column index - 1)]
= array address + 6*[ (3-1)*6 + (4-1) ]
| Row-major indexing, Column-major indexing
한 행을 먼저 끝내고, 다음 행으로 넘어간다 vs 한 열을 먼저 끝내고, 다음 열로 넘어간다
| O(1), O(n) Operation
- Array 끝에 추가 & 삭제하는거 : Order 1 (O(1)) operation : 변경 필요한 숫자 1개만 update 한다
- Array 시작/ 중간에 추가 & 삭제 : Order n (O(n)) operation : 맨 앞에 추가/ 삭제하면 뒤에 얘들을 다 앞으로 옮겨야되니까
2. Singly - Linked List
리스트는 연속일 필요는 없다. 드문드문 있더라도, Pointer 로 가리켜주면 되니까
각 노드는 key를 가지고 있다 & 다음 노드를 가리키는 indexed pointer 가 있다
PushFront(Key) : Add an element to the front of the list
Key TopFront() : return the front item
PopFront() : remove the front item
PushBack(Key) : add to back (append이기도 하다)
Key TopBack() : return the back item
PopBack() : remove back item
매우 비슷하지만, runtime은 다르다
Boolean Find(Key) : is key in list?
Erase(Key) : remove key from list
Boolean Empty : is list empty?
AddBefore(Node, Key) : add key before node
AddAfter(Node, Key) : add key after node
| Time for some operatoins
1. PushFront
26 Key 노드를 추가한다 - Pointer를 추가한다 - Head pointer를 연결해준다
새로운 노드 지정
새로운 노드의 키 지정 : 26
26의 포인터를 원래head가 가리키고 있던 7에 연결
현재의 head가 26을 가리키도록 한다
2. PopFront
Head pointer를 업데이트한다(삭제할 놈에서 연결해제하고, 그 뒤에 있는애랑 연결) - 맨 앞에 있던 26번 노드를 삭제한다
TopFront O(1): 가장 맨 앞에 있는 애들 return 한다 & PopFront : O(1)
head 포인터를 다음 노드에 연결 (26에서 7로 연결)
3. PushBack (no tail pointer) : 비싸다
Head에서부터 시작해서 End를 가야됨 : O(n)
맨 마지막거를 Pop한다 : O(n)
4. PushBack (with tail pointer) : 더 싸다 O(1)
추가하는 노드 8과 Key를 추가한다 - 맨 뒤에 있던 애가 8을 가리키도록 pointer 를 업데이트 한다 - tail pointer를 업데이트 한다
새로운 노드 생성
키 지정 8
그 노드의 포인터는 없는 것으로
꼬리가 없다면, head, tail이 new node를 가리키도록 한다
원래 마지막에 있던 노드 13 의 pointer를 새로운 8 에 연결시킨다
tail의 pointer도 8에 연결시킨다
tail pointer가 있으므로 앞에서부터 가지 않아도, 바로 tail을 찾을 수 있기 때문에 더 저렴하다
5. PopBack (with tail) O(n)
8을 가리키던 tail pointer를 그 앞에 있는 13에 연결 (근데 어떻게 13으로 가?)
우리는 13 -> 8 포인터가 있는거지, 8 -> 13 포인터가 있는게 아니야. 지금 있는 포인터는 뒤로 돌아가는 걸 도와주지 않는다.
그래서 다시 Head 에서부터 시작해서 13을 찾아야 하고, 그걸 tail pointer 가 잇도록 한다 ( O(n) )
그 다음에 8 노트를 없애는 거다
Q)
The loop will start with p pointing to the node containing key a.
How many times will the body of the while loop be executed?
a -> b -> c -> d
A) 2번
p.next.next : c (not nil) -> p는 b를 가리킨다
p.next.next : d (not nil) -> p는 c를 가리킨다
p.next.next = nil -> 종료하고 p는 d를 가리킨다
6. AddAfter
node2 : 새로운 55번 노드 생성, 키 부여
55번 노드의 pointer를 4번에 연결
10번 노드 pointer를 55에 연결
만약 10이 마지막 노드였으면
tail의 포인터를 10에서 55로 바꿔준다
| Summary
3. Doubly-Linked List
그럼 비용을 절약하는 방법은 없을까? 우리가 앞으로 가는 법이 없어서 비용이 들었던거잖아
그래서 bidirectional pointer가 생겨난거다
Key & Next pointer & Prev Pointer
Pop Back 하려면 바로 tail을 4로 보낼 수 있다 - 4와 13을 연결하던 pointer들을 삭제한다 - 13을 삭제한다
새로운 노드를 생성 : 13
tail이 없었다면 (애초에 다른 노드가 없었다면)
head, tail이 13 노드를 가리키도록 pointer
Pointer
기존 tail이던 4 -> 13 (next)
13 -> 기존에 tail이었던 4번 (prev)
tail -> 새로운 13을
tail 이 (원래 tail이던 13의 prev인) 4를 가리키도록 한다
( 여기서 tail은 13 )
새로운 tail이 된 4가 13을 가리키고 있던 tail.next pointer를 없애준다
Summary
