4. 자료구조 - 연결리스트의 종류

2018.11.07 (수)

DS - 연결리스트의 의미와 기본 유형

1. 연결리스트란 ?

   • 연결리스트는 값을 담는 '데이터'node와 다음 node로 이어지는 '링크'node 부분으로 이루어진다.

2. 연결리스트의 기본 유형 3가지

   • 단일 연결 리스트 , 이중 연결 리스트 , 원형 연결 리스트
   • 구성되는 방법에 따라서 종류가 나뉘어 지고 구성 방법은 다음과 같다. 

3. 단일 연결 리스트

   • 단일 연결 리스트는 링크node가 다음값만 가리키므로 한방향으로만 진행된다.
   • 때문에, 완전 종주를 하기 위해서는 처음 원소부터 진행하여야한다.
   • 항목 탐색시, 순차 탐색 필요.

4. 이중 연결 리스트

   • 단일연결리스트가 한 방향으로만 진행되는 단점을 극복하기 위하여 출현.
   • 두개의 링크node를 가지고 있어서 양방향으로 진행 가능하지만 두개의 레퍼런스를 요구하기때문에 복잡하다는 단점이 있다.

5. 원형 연결 리스트

   • 시작값이 마지막값이라는 특징을 가지고있다. 처음이자 마지막 부분을 구별하기 위해서 last값이 필요하다.
   • last값은 리스트 출력시 마지막을 알리는 역할이며 항목 추가 기준이 된다.
   • 리스트 종주 문제시 무한 루프 생성에 주의하여야 한다.