플랫폼: 프로그래머스
강의명: 어서와! 자료구조와 알고리즘은 처음이지?
강사명: 이시윤
1. ADT
추상적 자료구조
- 추상적("내부 구현은 숨겨두고")
- 자료구조(외부에 보이는 것들을 제공)
ex) 데이터와 연산
2. 연결 리스트
연결 리스트의 ADT를 위해 두 개의 클래스가 필요하다.
노드 클래스와 연결 리스트 클래스다.
노드 클래스는 데이터를 저장하는 자료구조이며,
연결 리스트 클래스는 데이터의 연산과 관련된 기능을 제공하는 자료구조다.
- 특정 원소 조회
- 연결 리스트 순회
- 연결 리스트 길이
- 특정 위치에 원소 삽입
- 원소 삭제
- 두 연결 리스트 합치기
3. 순회 구현
"""
추상적 자료구조로 LinkedList 라는 이름의 클래스가 정의되어 있다고 가정하고,
이 리스트를 처음부터 끝까지 순회하는 메서드 traverse() 를 완성하세요.
메서드 traverse() 는 리스트를 리턴하되,
이 리스트에는 연결 리스트의 노드들에 들어 있는 데이터 아이템들을 연결 리스트에서의 순서와 같도록 포함합니다.
예를 들어, LinkedList L 에 들어 있는 노드들이 43 -> 85 -> 62 라면, 올바른 리턴 값은 [43, 85, 62] 입니다.
이 규칙을 적용하면, 빈 연결 리스트에 대한 순회 결과로 traverse() 메서드가 리턴해야 할 올바른 결과는 [] 입니다.
"""
import unittest
from typing import List
class Node:
def __init__(self, data) -> None:
self.data = data
self.next = None
class LinkedList:
def __init__(self) -> None:
self.head = None
self.tail = None
self.len = 0
def traverse(self) -> List:
res = []
cur = self.head
while cur:
res.append(cur.data)
cur = cur.next
return res
class 연결리스트_순회_테스트(unittest.TestCase):
def test_빈_연결리스트는_빈_배열을_리턴한다(self):
linked_list = LinkedList()
actual = linked_list.traverse()
expected = []
self.assertEqual(actual, expected)
if __name__ == "__main__":
unittest.main()
4. 배열과의 비교
| 배열 | 연결 리스트 | |
|---|---|---|
| 저장 공간 | 연속한 위치 | 임의의 위치 |
| 특정 원소 참조 | O(1) | O(n) |
