개념 확인: Linked-List Operations

문제 1~4는 다음 단일 연결리스트에서 각각 따로 시작한다.

head → 12 → 5 → 17 → 8 → 30 → None 

def size(head):
    count = 0
    current = head
    while current is not None:
        count += 1
        current = current.next
    return count

1. size(head)의 while 반복이 몇 번 실행되고, 반복이 끝나는 조건이 무엇인지 적는다.
2. 인덱스 3인 노드에 가려면 head에서 next를 몇 번 따라가야 하고, 그 노드의 값은 무엇인지 적는다.
3. 배열과 연결리스트에서 전체 순회가 끝나는 조건을 각각 적는다.
4. 목록의 각 원소마다 목록 전체를 다시 훑어 같은 값의 개수를 세는 작업의 비용을 적는다.

문제 1의 단일 연결리스트에서 새로 시작한다.

search(head, target)은 앞에서부터 값을 비교하고 같으면 True를, None에 이르면 False를 반환한다.

1. target이 12, 17, 30, 99일 때 각각의 비교 횟수와 반환값을 적는다.
2. 원소가 n개일 때 최선·최악의 비교 횟수와, 찾는 값이 목록에 있고 위치가 고르게 분포할 때의 평균 비교 횟수를 적는다.
3. 값이 목록에 없음을 확인하려면 모든 노드를 비교해야 하는 이유를 적는다.

문제 1의 단일 연결리스트에서 새로 시작한다.

1. 값 5인 노드(previous)와 값 17인 노드(current) 사이에 새 노드 31을 넣는다. 고쳐야 할 참조 두 개의 올바른 실행 순서를 한 가지 적는다.
2. 한 구현이 previous.next = new를 먼저 실행한 뒤 new.next = previous.next를 실행했다. 결과가 어떻게 되는지 적는다.
3. 맨 앞에 새 노드 40을 넣을 때 head = new를 먼저 실행하면 무엇을 잃는지 적고, 올바른 순서를 적는다.
4. 인덱스 i에 삽입하는 비용을 자리 찾기와 연결 고치기로 나누어 적는다.

문제 1의 단일 연결리스트에서 새로 시작한다.

1. 값 17인 노드를 삭제할 때 previous와 current가 가리키는 노드와, 바꿀 참조 하나를 적는다.
2. 삭제 뒤 목록을 head부터 적고, 노드 17이 목록에서 어떤 상태가 되는지 적는다. 이어 마지막 노드 30을 지울 때 previous.next를 무엇으로 바꾸는지 적는다. 목록 객체가 tail도 저장한다면 tail은 어디로 옮기는가?
3. 첫 노드 12를 삭제할 때 previous가 무엇이고 대신 무엇을 고쳐야 하는지 적는다.

head만 저장한 단일 연결리스트에 원소가 1,000개 있다.

1. 다음 연산마다 비용을 Θ 표기로 적고, 비용을 결정하는 작업을 적는다. 맨 앞에 삽입, 인덱스 700에 삽입, 인덱스 700에서 삭제, 목록에 없는 값 탐색.
2. 인덱스 700에 삽입할 때 연결을 고치는 일은 참조 두 개인데도 전체 비용이 Θ(1+i)인 이유를 적는다.
3. 합을 구하는 순회와 최댓값을 구하는 순회를 따로 한 번씩 하는 작업과, 각 원소마다 목록 전체를 다시 훑는 작업의 비용을 비교한다.