자료구조(15) - 연결리스트의 종류와 특성
- 순서 리스트
:자료의 논리적인 순서와 물리적인 순서가 일치하는 구조
: 배열을 이용하여 구현.
: 삽입, 삭제 연산후에 연속적인 물리주소를 유지하기위해 원소들을 이동시키는
추가적인 작업과 시간이 소요
: 시간복잡도 O(n)
- 단순 연결 리스트
: 노드로 구성
: 데이터 부분 + 링크 부분
: 데이터 부분 : 저장되는 원소, 원소의 형태에 따라 하나 이상의 필드
: 링크 부분 : 다음 노드의 위치를 가리키는 포인터 값 저장.
: 다음 노드가 없는 마지막 값의 경우 null 값.
: 원소의 삽입과 삭제시 각각의 링크 부분의 포인터 값만을 변경하면 된다.
: 시간복잡도 O(1)
: 연속적인 기억공간이 없어도 저장이 가능하다.
: 순서리스트나 배열보다 링크부분이 추가되므로, 기억공간이 많이 필요하다.
: 알고리즘 구현이 복잡하다.
: 특정노드 검색 시 무한루프에 빠질 수 있다.
- 이중 연결 리스트
: 단순 연결 리스트는 선행 노드를 찾기 힘들고, 삽입 삭제시에 선행 노드가 반드시 필요하다.
또한, 리스트의 연결 방향으로만 탐색이 가능하므로 역으로 탐색하는 것이 불가능하다.
: 이중 연결 리스트는 양방향으로의 탐색이 가능하도록
두 개의 링크 필드를 갖는 노드로 구성한 리스트이다.
: 이로인해, 임의의 후속 노드 뿐 아니라, 선행 노드를 탐색할 수 있는 리스트.
: llink, rlink ( 왼쪽 노드와 연결, 오른쪽 노드와 연결 ) 의 두개의 링크를 갖고,
데이터필드를 갖는다.
: 헤드노드도 두개의 링크 필드를 갖는다.
: 초기의 헤드노드만 있을 때에는 링크 필드는 자기 자신을 가리킨다.
- 일반 리스트
: 0개 이상의 원소 또는 서브 리스트를 갖는 유한 순차 리스트 입니다.
: 일반 리스트의 표현은
L = (e1, e2, e3, e4, ..... en ) 으로하고 L은 리스트의 이름이며,
n은 리스트 내의 원소의 갯수, n >=1인 경우의 첫번째 원소는 L의 head이며 head(L)이라 표현
첫 원소를 제외한 원소를 L의 tail이라 하며 tail(L)이라 표현한다.
: 공백 리스트에 대해서는 head, tail을 정의하지 않으며, 정의 속에 다시 리스트를 사용하고 있기 때문에
순환적 정의이다.
: A( a, (b, c) )는 길이다 2이고, 첫 원소는 a이고 두번쨰 원소는 서브리스트 ( b, c )dlek.
리스트 A에 대해 head(A) = a, tail(A) = ( (b, c) ) 로 표현한다.
B ( A, A, () )는 길이가 3이고, 처음 두 원소는 서브 리스트 A이고, 세번째 원소는 공백 리스트이다.
C ( a, C() ) 는 길이가 2인 순환 리스트이고 C는 (a,(a,(a,(a,..) 에 해당한다.
D = ()는 길이가 0인 null 또는 공백 리스트 라고 한다.