<div class="warning"> 여기사 사용된 그림및 플래쉬 자료에 대한 저작권은 전북대학교 박순철 교수님께 있습니다. </div>

정의#

Linked List는 데이터를 저장하는 부분과 다음 데이터의 위치를 저장하는 부분인 포인터로 구성된 자료구조이다. 배열과 달리 다음 데이터의 위치를 지정하는 포인터를 사용하기 때문에 데이터의 연결성을 보장한다. 정렬시 데이터의 이동없이 포인터에 대한 작업으로 간단히 정렬작업이 이루어질수 있다.

Single Linked List#

다음은 Single Linked List를 나타내는 그림이다. 그림에서 볼수 있듯이 바로 뒤에 위치하는 데이터를 가리키는 포인터를 가지고 있다.

1.jpg

기본적인 구조를 이해했다면 입력및 출력시 어떤형태로 처리가 되는지 보자.

<object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://active.macromedia.com/flash4/cabs/swflash.cab#version=4,0,0,0" width="500" height="250"> <param name="movie" value="http://internet512.chonbuk.ac.kr/datastructure/link/flash/single_list.swf"> <param name="play" value="false"> <param name="loop" value="false"> <param name="quality" value="high"> <embed src="http://internet512.chonbuk.ac.kr/datastructure/link/flash/single_list.swf" play="false" loop="false" quality="high" pluginspage="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash" width="500" height="250"></embed> </object>

Circular Linked List#

다음은 Circular Linked List를 나타내는 그림이다. 바로 뒤에 위치하는 데이터를 가리키는 포인터를 가지고 있지만 앞의 Single Linked List와는 달리 원형으로 되어 있다. Single Linked List의 경우 마지막 데이터는 포인터 값이 null인 반면에 이 Circular Linked List는 마지막 데이터가 가지는 포인터의 값은 가장 앞 데이터의 위치를 가리키는 값이 된다. Single Linked List의 경우 데이터가 끊기는 점으로 인한 문제점을 가질수 있으나 Circular Linked List는 그런 문제점이 좋재하지 않게 된다.

2.jpg

기본적인 구조를 이해했다면 처리방식을 한번 보자.

아래의 두개의 예제는 삽입시 이루어지는 작업이다.

<object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://active.macromedia.com/flash4/cabs/swflash.cab#version=4,0,0,0" width="500" height="250"> <param name="movie" value="http://internet512.chonbuk.ac.kr/datastructure/link/flash/circular_list(new).swf"> <param name="play" value="false"> <param name="loop" value="false"> <param name="quality" value="high"> <embed src="http://internet512.chonbuk.ac.kr/datastructure/link/flash/circular_list(new).swf" play="false" loop="false" quality="high" pluginspage="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash" width="500" height="250"></embed> </object>

<object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://active.macromedia.com/flash4/cabs/swflash.cab#version=4,0,0,0" width="500" height="250"> <param name="movie" value="http://internet512.chonbuk.ac.kr/datastructure/link/flash/circular_list_01(new).swf"> <param name="play" value="false"> <param name="loop" value="false"> <param name="quality" value="high"> <embed src="http://internet512.chonbuk.ac.kr/datastructure/link/flash/circular_list_01(new).swf" play="false" loop="false" quality="high" pluginspage="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash" width="500" height="250"></embed> </object>

아래의 경우에는 삭제시 이루어지는 작업이다.

<object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://active.macromedia.com/flash4/cabs/swflash.cab#version=4,0,0,0" width="500" height="250"> <param name="movie" value="http://internet512.chonbuk.ac.kr/datastructure/link/flash/circular_list_delete(new).swf"> <param name="play" value="false"> <param name="loop" value="false"> <param name="quality" value="high"> <embed src="http://internet512.chonbuk.ac.kr/datastructure/link/flash/circular_list_delete(new).swf" play="false" loop="false" quality="high" pluginspage="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash" width="500" height="250"></embed> </object>

결과적으로 Circular Linked List는 다음과 같은 장점과 단점을 가지게 된다.

  • 장점
    • 임의의 노드로부터 모든 노드로의 접근이 용이하다.
    • 리스트에 노드를 삽입하거나 삭제할때 노드수에 관계없이 거의 일정한 시간이 소요되므로 노드의 삽입과 삭제 연산이 편리하다.
    • 리스트의 결합, 분리 작업을 효율적으로 수행할수 있다.
  • 단점
    • 리스트를 구성하는 특정 노드를 검색하고자 할 때 잘못하면 무한 루프에 빠질 가능성이 있으므로, 검색을 끝낼 수 있는 노드가 존재하여야 하며 이런 목적으로 추가된 노드를 HEAD노드라고 한다.

Double Linked List#

다음은 Double Linked List를 나타내는 그림이다. Single Linked List가 뒤에 위치하는 데이터의 위치값만을 가진다면 이 Double Linked List는 앞과 뒤 데이터의 위치를 표시하는 포인터를 모두 가진다고 보면 된다.

3.jpg

기본적인 구조를 이해했다면 입력및 출력시 어떤형태로 처리가 되는지 보자.

<object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://active.macromedia.com/flash4/cabs/swflash.cab#version=4,0,0,0" width="500" height="250"> <param name="movie" value="http://internet512.chonbuk.ac.kr/datastructure/link/flash/double_list_insert(new).swf"> <param name="play" value="false"> <param name="loop" value="false"> <param name="quality" value="high"> <embed src="http://internet512.chonbuk.ac.kr/datastructure/link/flash/double_list_insert(new).swf" play="false" loop="false" quality="high" pluginspage="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash" width="500" height="250"></embed> </object>

결과적으로 Double Linked List는 다음과 같은 장점과 단점을 가지게 된다.

  • 장점
    • 임의의 노드를 검색할 때 양 방향으로 접근할 수 있다.
    • 임의의 노드의 연결이 파괴되었을 때 복구가 가능하다.
  • 단점
    • 전위와 후위 연결을 위한 포인터 기억 공간이 필요하다.

Doubly Circular Linked List#

다음은 Doubly Circular Linked List를 나타내는 그림이다. 이 Linked List는 Circular Linked List와 Double Linked List를 혼합한 형태이다. 즉 앞과 뒤의 데이터를 가리키는 포인터를 가지고 있으며 마지막 데이터를 기준으로 뒤의 데이터는 가장 앞의 데이터가 된다.

4.jpg

결과적으로 Doubly Circular Linked List는 다음과 같은 장점과 단점을 가지게 된다.

  • 장점 : 연결리스트의 모든 장점을 가지고 있으며 가장 융통성이 좋다.
  • 단점 : 대단히 복잡하고 가장 많은 공간이 필요하다.

Add new attachment

Only authorized users are allowed to upload new attachments.

List of attachments

Kind Attachment Name Size Version Date Modified Author Change note
jpg
1.jpg 39.6 kB 1 16-Jul-2007 15:11 DongGukLee
jpg
2.jpg 31.8 kB 1 16-Jul-2007 15:24 DongGukLee
jpg
3.jpg 21.0 kB 1 16-Jul-2007 15:45 DongGukLee
jpg
4.jpg 25.3 kB 1 16-Jul-2007 15:45 DongGukLee
« This page (revision-6) was last changed on 16-Jul-2007 15:45 by DongGukLee  
G’day (anonymous guest) My Prefs

Referenced by
Basic

JSPWiki v2.8.4