[자료구조] 리스트(List)에 대한 고찰

리스트(List)는 무엇인가?

---

리스트(List) : 어떤 자료의 원소(node, atom) 단위로 구성된 집합을 말하며 삽입과 제거가 가능한 순서적 자료의 집합이다.

 

리스트(List)는 크게 2개로 나눌 수 있다.

 

 

1. 선형리스트 (Linear List)

 

  1) 장점

    -  가장 간단한 리스트 구조

    -  순서적으로 검색하므로 Access time이 빠름

    -  기억 공간의 효율은 밀도 1로 가장 좋음

    

  2) 단점

    -  중간에 노드의 삽입과 제거가 어려움

    -  기억 장소로부터 종속적

    -  삽입과 제거가 번거로움

 

 

2. 연결리스트 (Linked List)

 

  1) 장점

    -  링크 부분의 주소만 변경하면 되므로 노드의 삽입과 삭제가 용이

    -  링크 포인터로 검색하므로 연속적으로 기억 공간이 없어도 노드의 저장이 가능

 

  2) 단점

    -  Access time이 느림

    -  알고리즘 구현이 복잡함

    -  링크 포인터를 사용하므로 연결 리스트가 배열보다 기억 공간이 많이 필요

 

  3) 연결리스트의 종류

    -  단일 연결 리스트 (Singly linked linear list)

    -  환상 연결 리스트 (Circularly linked linear list)

    -  이중 연결 리스트 (Doubly linked linear list)

    -  이중 환상 연결 리스트 (Doubly circularly linked linear list)