[자료구조] 연결리스트

선형적인 자료구조 연결리스트에 대해 정리

연결 리스트

• 선형 자료구조
• 동적으로 새로운 노드를 삽입하거나 삭제하기 간편하다.
• 메모리에 물리적인 순서대로 저장되지는 않는다.
• 단, 탐색에는 O(n)이 소요된다.

deque

• python의 list에서 pop(0)을 통해 맨 앞의 원소를 뽑아내는 것은 비효율적이다. list의 원소들이 하나씩 shifting되기 때문이다.
• 따라서 collections.deque()를 이용하면 좋다.
• q.append(some value)를 하고 q.popleft(), q.pop() 이런식으로 앞뒤에서 빠르게 원소를 뽑아낼 수 있다.

Python code 예시

• Link
• 펠린드롬 연결 리스트
  • deque, 러너 이용
• 두 정렬 리스트의 병합
  • 재귀 이용
• 역순 연결 리스트 1
  • 반복 구조로 뒤집기
• 두 수의 덧셈
• 페어의 노드 스왑
• 홀짝 연결 리스트
• 역순 연결 리스트 2

Reference

• 파이썬 알고리즘 인터뷰 (박상길 지음)