[Python 자료구조] 연결 리스트(Linked List)

⭐ 연결 리스트

1. 선형 배열 vs 연결 리스트

선형 배열 (linear array)

• 번호가 붙여진 칸에 원소들을 채워넣는 방식
• 특정 원소를 지칭하는게 매우 간편하다 : O(1)

연결 리스트 (linked list)

• 각 원소들을 줄줄이 엮어서 관리하는 방식
• 특정 원소를 지칭하는게 선형탐색과 유사하다 : O(n)

2. 원소 삽입

• insertAt()

def insertAt(self, pos, newNode):

# pos는 포지션을 의미
# pos의 위치는 1<=pos<=nodeCount+1 # 1이상이고 맨 마지막 노드보다 더 뒤에 들어가는 경우
# pos 위치에 newNode 삽입 -> 성공/실패 True/False 리턴

def insertAt(self, pos, newNode):
	prev = self.getAt(pos-1) # 시작점 prev를 지정하고
	newNode.next = prev.next # prev.next를 newNode.next로 옮기고
	prev.next = newNode # prev.next를 newNode에 연결
	self.nodeCount += 1 # nodeCount를 1씩 더해가기