linked list

• 배열처럼 선형 자료 구조이지만, 연속한 메모리 위치에 값이 저장되지 않는다.
• 단일 연결 리스트(Singly Linked List)는 노드(Node)를 연결한 것으로 노드는 값과 다음 노드의 주소를 저장한다.

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

배열은 인덱싱으로 원소에 쉽게 접근할 수 있다. 하지만, 원소를 추가 및 삭제하기 위해서는 연속한 메모리 공간을 확보하고 원소를 이동시켜야 하므로 시간이 오래 걸린다.
자료의 양이 정해져 있지 않거나 자료를 추가/삭제할 일이 많다면 연결 리스트가 적합하다.

연결 리스트의 특징

• 동적 배열
• 삽입과 삭제가 쉽다
• 스택, 큐 등의 자료 구조를 만들 때 사용한다.

연결 리스트 만들기

1. 첫째 노드를 만들고, head라는 이름표를 붙인다.
2. 둘째 노드를 만들고, head의 next가 둘째 노드를 가리키도록 한다.
3. 셋째 노드를 만들고, head의 next의 next가 셋째 노드를 가리키도록 한다.

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

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

연결 리스트의 값을 출력하기

• head부터 마지막 노드까지 이동하면서 data를 출력한다.
• 이때 head는 연결 리스트의 시작이므로 head가 이동하면 연결 리스트를 잃게 된다.
• 따라서 변수를 만들고 head부터 마지막 노드까지 이동하면서 data를 출력한다.
• 마지막 노드의 next는 None을 가리키므로 노드가 None이 아닐 동안 계속 이동하면서 data를 출력한다.

node = head
while node:
	print(node.data, end = " ")
    node = node.next

연결 리스트의 끝에 새 노드를 추가하기

1. 변수를 만들고 head부터 마지막 노드까지 이동한다.
2. 마지막 노드의 next가 새 노드를 가리키도록 한다.

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

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

node = head
while node:
	if node.next is None:
    	node.next = Node(4)
        break
    node = node.next

연결 리스트의 처음에 새 노드를 추가하기

1. 추가할 노드를 생성한다
2. 추가할 노드의 next가 head를 가리키게 한다.
3. head를 추가한 노드로 옮긴다.

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