List 자료구조

List

데이터의 목록을 다루는 자료구조

간단하면서 활용도가 높고 다른 자료구조의 기초

배열처럼 데이터 집합을 보관하는 기능을 가지면서 배열과는 달리 유연하게 크기 바꿀 수 있음

• Node (마디)

  리스트 내의 각 요소

• 종류

  • Linked List(연결 리스트)

    리스트 구현 중 가장 간단한 방법

    노드를 연결해서 만드는 리스트

    node 조회는 앞 node 에서 뒷 node 방향으로 1방향

    제일 앞쪽의 node에 앞의 노드를 추가하는 것은 O(1) 의 시간 복잡도 지님

    제일 뒷쪽의 node에 뒤의 노드를 추가하는 것은 O(n) 의 시간 복잡도 지님

  • Doubly Linked List (이중 연결 리스트)

    node 조회는 앞 node 에서 뒷 node 서로 양방향

    linked list 의 탐색 기능을 개선해서 시간 복잡도 낮출 수 있음

    양방향 조회로 인해 변수를 추가로 사용하며 메모리 추가 사용

  • Circular Linked List (원형 연결 리스트)

    테일은 헤드의 ‘앞 node’, 헤드는 테일의 ‘뒷 node’

    무한 루프에 빠질 경우 있으므로 종료되는 node 설정 권장