[기초 데이터 구조] 배열, 연결리스트, 단일연결리스트

-배열

: 행우선 등등

 

-연결리스트

: 동적메모리에 할당된, 링크에 의해 연결된 유한 개수의 데이터원소 노드들

 

-종류

: 단일연결리스트

이중연결리스트

원형연결리스트

헤더 및 트레일러 연결리스트

이들의 복합

 

1. 단일연결리스트

-연속 노드로 구성된 가장 단순한 연결 데이터구조

 

노드의 저장내용

: 데이터원소, 링크(다음노드의 주소)

 

접근점

:첫 노드 즉, 헤드노드의 주소

 

2. 이중연결리스트

-추가 링크를 사용하여 역방향 순회도 가능한

 

노드의 저장내용

: 원소(element), 링크(다음 노드의 주소), 링크(이전 노드의 주소)

 

접근점

:헤드노드, 테일노드

 

3. 원형연결리스트

-마지막 노드의 링크가 헤드노드의 주소

 

접근점

:헤드노드의 주소

 

4. 헤더와 트레일러

-헤드노드 바로 앞에 특별한 헤더(header)노드를 추가하여 작업편의성 ^

-테일노드 바로 뒤에 트레일러(trailer)노드 추가 가능한

-특별노드 저장내용 >> 더미노드(dummy element, 모조 원소)

-접근점 : 헤더노드 또는 트레일러 노드의 주소

 

5.기타 연결리스트

-원형헤더연결리스트

-원형이중연결리스트