연결 리스트는 노드(Node : 마디)들을 연결한 것

---

1. 노드(Node)

• 노드는 값과 다음 노드의 주소를 가진다(저장한다).
  • head가 첫 번째 노드의 주소를 가리킨다.

- 노드 클래스 정의

class Node:
 def __init__(self, data, next):
     self.data = data        # data : 현재 노드의 값을 가리키는 변수(속성, attribute)
     self.next = None        # next : 다음 노드의 주소를 가리키는 변수

• 

---

2. 연결리스트 가볍게 느낌 보기

- 노드 생성하고 연결

class Node:
    def __init__(self, data):	# 파라미터(변수)를 데이터 하나만 받음.
        self.data = data        # data : 현재 노드의 값을 가리키는 변수(속성, attribute)
        self.next = None        # next : 다음 노드의 주소를 가리키는 변수

# 1. head라는 첫 번째 노드(인스턴스)를 만든다.
head = Node(1)

# 2. head의 next(다음 노드의 주소)에 두 번째 노드를 할당한다. : 두 번째 노드(인스턴스) 생성
head.next = Node(2)

# 3. head.next의 next(다음 노드의 주소)에 세 번째 노드를 할당한다. : 세 번째 노드(인스턴스) 생성
head.next.next = Node(3)

• 

• 연결리스트에 노드 추가하기

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

head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

# 앞에 추가
1) 추가할 Node(인스턴스) 생성해서 변수(new_node)에 할당
2) 추가할 Node new_node의 next가 head를 가리키도록 new_node.next의 값에 head를 할당
3) 이제 새로 추가해준 Node가 head가 되도록 head에 new node를 할당

new_node = Node(0)
new_node.next = head
head = new_node

• 

# 뒤에 추가
- 연결리스트는 뒤의 메모리 박스로 접근하려면 첫 번째 박스로 가서 순차적으로 접근할 수 밖에 없다.
- 연결리스트 끝에 노드를 추가하기 위해 head.next.next....next = Node(data) 이렇게 하기에는 비효율적이다.
1) 변수에 head를 할당
2) node.next가 None일 때까지 반복하며 마지막 Node까지 이동
3) 마지막 node.next에 new_node를 할당

new_node = head					# 추가할 Node의 위치를 head에 놓고 
While new_node.next:			# new_node.next 값이 있는한 계속 반복
	new_node = new_node.next 	# next 값에 new_node를 할당하면서 위치 이동 = 마지막 위치는 next값이 None

new_node.next = Node(4)			# next값이 None이 되었을 때 next의 값에 데이터 값 할당

•