선형리스트에서 발생하게 되는 원소들의 이동문제를 해결해주는 방법은 리스트를 구성하는 연속된 순서의 원소들이 기억장소내에서 어느곳에나 저장 가능하도록 원소들의 위치와 무관하게 원소들을 연결하여 표현하는 방법이다.

연결리스트에서는 원소들의 값이외에 포인터값이 포함되므로 리스트의 한원소의 노드(node)는 원소값을 저장하는 자료(data)부분과 다음 원소를 지적하는 포인터값을 저장 하는 링크(link) 부분으로 구성된다.
                   

단일 연결 리스트의 구조

입력, 출력시에 어떠한 변화가 있는지 볼 수 있다.

풀이)

주소	1	2	3	4	5	6	7	8	9	10
데이터	장	박	강	김 (*2)	이	최	남	오
링크	3	10	4  (*1)	5  (*2)	9	1	2	마지막

(*1) - 노드의 삽입으로 인해 변경된 링크 필드값
(*2) - 새로 삽입된 노드

<노드 삽입 알고리즘>

Procedure INSERT_node (Head, Item, X)
   // Head : 연결 리스트의 첫 번째 노드를 가리키는 포인터 //
   // Item : 새로 삽입할 데이터 항목 //
   // X : 임의의 노드를 가리키는 포인터 //

call GETNODE(Y)
   DATA(Y) ← Item
   if (Head=Nil) then
     Head ← Y
     LINK(Y) ← Nil
   else
     LINK(Y) ← LINK(X)
     LINK(X) ← Y
   end INSERT_node

데이터 "항목 C와 F사이에 새로운 "데이터 항목 E"를 삽입하는 과정은 다음과 같다.  이 때, X는 포인터이며 X가 가리키는 노드의 다음 노드에 새로운 노드를 삽입하기 위해 사용된다.

• 새로운 노드를 생성한 후, 생성된 노드의 주소를 포인터 변수 Y에 대입한다.
• 생성된 노드에 데이터 항목 E를 대입한다.
• X가 가리키는 노드의 링크 값을 생성된 노드의 링크 부분에 대입한다.
• 생성된 노드의 주소를 가리키는 Y값을 X가 가리키는 노드의 링크 부분에 대입한다.

<예제 2.>

단일 연결 리스트에서 다음과 같은 리스트의 삭제가 이루어질 때 비연속적인 리스트로 표현하시오.

주소	1	2	3	4	5	6	7	8	9	10
데이터	장	박	삭제	김	이	최	남	오
링크	5  (*1)	10	삭제	5	9	1	2	마지막

(* 1) - 노드의 삭제로 인해 변경된 링크 필드값

Procedure DELETE_node (W, X Head)
   // W : 삭제할 노드의 앞 노드를 가리키는 포인터 //
   // X : 삭제할 노드를 가리키는 포인터//
   // Head : 연결 리스트의 첫 번째 노드를 가리키는 포인터//

   if (W=Nil) then  
     Head ← LINK(Head)
   else
     LINK(W) ← LINK(X);
   call RET(X)
end DELETE_node

X가 가리키는 노드를 삭제하는 과정은 다음과 같다.
  이 때, W는 삭제하고자 하는 노드의 앞 노드를 가리킨다.

① X가 가리키는 링크 값을 W가 가리키는 노드의 링크 부분에 대입한다.
      LINK(W)←LINK(X)

② X가 가리키고 있는 노드를 가용 기억공간으로 되돌린다.
      즉 X 노드는 단순 연결 리스트에서 삭제된다.
      call RET(X)

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

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.