개념 확인: Linked-List Representation

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

a = Node(7)
b = Node(3)
c = Node(9)
a.next = c
c.next = b

1. 노드를 만든 순서와 a에서 next를 따라 읽은 값의 순서를 각각 적는다.
2. 마지막 노드와 그 노드의 next 값을 적는다.
3. 배열과 연결리스트에서 ‘다음 원소’를 찾는 단서가 각각 무엇인지 적는다.

문제 1의 Node 클래스를 쓴다.

u = Node(5)
v = u
v.data = 8
w = Node(8)

1. u.data, u is v, u is w, u.data == w.data의 결과를 적는다.
2. 이 코드가 만든 노드 객체는 몇 개인지 적는다.
3. v = u를 ‘노드를 복사한다’고 읽으면 어떤 판단이 틀리는지 적는다.

목록 객체는 head, tail, n을, 각 노드는 data, next를 저장한다.

1. 빈 목록일 때 head, tail, n을 적는다.
2. 원소 하나를 추가한 뒤 head와 tail의 관계와 n을 적는다.
3. 원소가 하나인 목록에서 그 노드를 목록에서 빼며 head만 None으로 바꾸고 tail은 그대로 두었다. 어떤 문제가 남는지 적는다. 삭제 전에 saved가 그 노드를 가리켰다면, 삭제 뒤 노드 객체의 존재와 목록 소속은 각각 어떻게 되는가?
4. tail과 n을 저장하지 않으면 끝 노드를 찾거나 원소 수를 셀 때 어떤 일이 필요한지 적는다.

다음 문장이 맞는지 판단하고, 틀리면 고친다.

1. 연결리스트도 배열처럼 만들 때 용량을 정하고 칸을 한꺼번에 확보한다.
2. 연결리스트의 노드들은 메모리에서 이어져 있어야 순서가 유지된다.
3. Python에서 노드 참조에 1을 더하면 다음 노드로 이동할 수 있다.
4. C의 NULL과 Python의 None은 가리키는 노드가 없음을 나타낸다.
5. Python에서는 어떤 이름으로도 도달할 수 없게 된 노드를 실행 환경이 회수한다.

원소 8개를 담은 목록을 배열과 연결리스트로 각각 표현했다.

1. 배열에서 인덱스 5의 원소를 읽을 때와 연결리스트에서 인덱스 5의 원소를 찾을 때 각각 어떤 내부 작업을 하는지 적는다.
2. 배열에서 인덱스 3에 새 원소를 넣으려면 어떤 추가 작업이 필요한지 적고, 옮기는 원소 수를 구한다.
3. 배열의 빠른 인덱스 접근과 가운데 삽입의 원소 이동이 같은 성질에서 나온다는 말의 뜻을 적는다.
4. 원소를 추가하거나 삭제할 때 배열의 칸과 연결리스트의 노드가 각각 어떻게 되는지 적는다.
5. 두 표현 가운데 하나를 고를 때 무엇을 기준으로 하는지 적는다.