독학사 컴퓨터과학과

자료구조(15) - 연결리스트의 종류와 특성

고유빙글 2021. 4. 19. 11:58

 - 순서 리스트

               :자료의 논리적인 순서와 물리적인 순서가 일치하는 구조

               : 배열을 이용하여 구현.

                         : 삽입, 삭제 연산후에 연속적인 물리주소를 유지하기위해 원소들을 이동시키는

                          추가적인 작업과 시간이 소요

                         : 시간복잡도 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 또는 공백 리스트 라고 한다.