연결 리스트는 노드(Node : 마디)들을 연결한 것
1. 노드(Node)
- 노드는 값과 다음 노드의 주소를 가진다(저장한다).
- 노드 클래스 정의
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의 값에 데이터 값 할당