Main Content

클래스를 사용하여 연결 리스트 구현하기

클래스 정의 코드

클래스 정의 코드 목록은 dlnode 클래스 개요 항목을 참조하십시오.

이 클래스를 사용하려면 이름이 @dlnode인 폴더를 생성하고 dlnode.m을 이 폴더에 저장하십시오. @dlnode의 부모 폴더는 MATLAB® 경로에 있어야 합니다. 또는, dlnode.m을 경로 폴더에 저장하십시오.

dlnode 클래스 설계

dlnode는 이중 연결 리스트를 생성할 때 사용되는 클래스입니다. 리스트의 각 노드에는 다음이 포함되어 있습니다.

  • 데이터 배열

  • 다음 노드에 대한 핸들

  • 이전 노드에 대한 핸들

각 노드에는 노드에 대한 다음 작업이 가능하도록 지원하는 메서드가 있습니다.

  • 연결 리스트에서 지정된 노드 앞에 삽입

  • 연결 리스트에서 특정 노드 다음에 삽입

  • 리스트에서 제거

클래스 속성

dlnode 클래스는 각 노드를 다음과 같은 세 개의 속성을 가진 핸들 객체로 구현합니다.

  • Data — 이 노드에 대한 데이터를 포함합니다.

  • Next — 리스트에서 다음 노드에 대한 핸들을 포함합니다(SetAccess = private).

  • Prev — 리스트에서 이전 노드에 대한 핸들을 포함합니다(SetAccess = private).

다음 도식에서는 세 개의 노드, 즉 n1, n2, n3으로 구성된 리스트를 보여줍니다. 또한, 노드가 다음 노드와 이전 노드를 어떻게 참조하는지도 보여줍니다.

Three nodes of a doubly linked list

클래스 메서드

dlnode 클래스는 다음 메서드를 구현합니다.

  • dlnode — 노드를 생성하고 Data 속성에 대한 입력값으로 전달된 값을 할당합니다.

  • insertAfter — 지정된 노드 뒤에 이 노드를 삽입합니다.

  • insertBefore — 지정된 노드 앞에 이 노드를 삽입합니다.

  • removeNode — 리스트에서 이 노드를 제거하고 나머지 노드를 다시 연결합니다.

  • clearList — 큰 리스트를 효율적으로 제거합니다.

  • delete — 리스트를 삭제할 때 MATLAB이 호출하는 프라이빗 메서드입니다.

이중 연결 리스트 생성하기

노드의 데이터를 dlnode 클래스 생성자에 전달하여 노드를 생성합니다. 예를 들어, 다음 명령문은 데이터 값으로 1, 2, 3을 갖는 세 개의 노드를 생성합니다.

n1 = dlnode(1);
n2 = dlnode(2);
n3 = dlnode(3);

이중 연결 리스트를 생성하는 용도로 설계된 클래스 메서드를 사용하여 이 노드를 이중 연결 리스트로 만듭니다.

n2.insertAfter(n1) % Insert n2 after n1
n3.insertAfter(n2) % Insert n3 after n2

이제 세 개의 노드가 연결되었습니다.

n1.Next % Points to n2
ans = 

  dlnode with properties:

    Data: 2
    Next: [1x1 dlnode]
    Prev: [1x1 dlnode]
n2.Next.Prev % Points back to n2
ans = 

  dlnode with properties:

    Data: 2
    Next: [1x1 dlnode]
    Prev: [1x1 dlnode]
n1.Next.Next % Points to n3
ans = 

  dlnode with properties:

    Data: 3
    Next: []
    Prev: [1x1 dlnode]
n3.Prev.Prev % Points to n1
ans = 

  dlnode with properties:

    Data: 1
    Next: [1x1 dlnode]
    Prev: []

연결 리스트에 핸들 클래스를 사용해야 하는 이유

각 노드는 고유하며, 따라서 어떤 노드의 이전 또는 다음에 똑같은 노드가 올 수 없습니다.

예를 들어, 노드 객체 node는 해당 Next 속성에 다음 노드 객체 node.Next의 핸들을 포함합니다. 마찬가지로, Prev 속성은 이전 노드 node.Prev의 핸들을 포함합니다. 이전 섹션에서 정의한 세 개 노드로 구성된 연결 리스트를 사용하여 다음 명제가 참임을 입증할 수 있습니다.

n1.Next == n2
n2.Prev == n1

이제 n2를 x에 할당한다고 가정하겠습니다.

x = n2;

그러면 다음 두 등식이 참이 됩니다.

x == n1.Next
x.Prev == n1

하지만 각각의 노드는 고유하므로 리스트에서 n1.Next와 일치해야 한다는 조건과 n1에 대한 핸들을 포함하는 Prev 속성을 가져야 한다는 조건을 충족할 수 있는 노드는 하나뿐입니다. 따라서 x는 n2와 동일한 노드를 가리켜야 합니다.

여러 변수가 동일한 객체를 참조할 수 있는 방법이 있어야 합니다. MATLAB의 handle 클래스는 x와 n2 둘 다 동일한 노드를 참조하게 해주는 수단을 제공합니다.

핸들 클래스는 eq 메서드를 정의합니다(핸들 클래스 메서드를 나열하려면 methods('handle')을 사용하십시오). 이 메서드를 통해 모든 핸들 객체에 == 연산자를 사용할 수 있습니다.

관련 정보

핸들 클래스에 대한 자세한 내용은 핸들 클래스와 값 클래스 비교 항목을 참조하십시오.

dlnode 클래스 개요

이 섹션에서는 dlnode 클래스의 구현에 대해 설명합니다.

예제 코드설명
classdef dlnode < handle

dlnode 클래스 설계

연결 리스트에 핸들 클래스를 사용해야 하는 이유

핸들 클래스와 값 클래스 비교 

   properties
      Data
   end
dlnode 클래스 설계
   properties (SetAccess = private)
      Next = dlnode.empty
      Prev = dlnode.empty
   end

속성 특성(Attribute): SetAccess.

dlnode 객체를 비우려면(empty) 이들 속성을 초기화합니다.

속성에 대한 일반적인 정보는 속성 구문 항목을 참조하십시오.

   methods

메서드에 대한 일반적인 정보는 클래스 설계 내 메서드 항목을 참조하십시오.

      function node = dlnode(Data)
         if (nargin > 0)
            node.Data = Data;
         end
      end

(연결되지 않은) 개별 노드를 생성하려면 데이터만 있으면 됩니다.

생성자에 대한 일반적인 정보는 생성자 관련 지침 항목을 참조하십시오.

      function insertAfter(newNode, nodeBefore)
         removeNode(newNode);
         newNode.Next = nodeBefore.Next;
         newNode.Prev = nodeBefore;
         if ~isempty(nodeBefore.Next)
            nodeBefore.Next.Prev = newNode;
         end
         nodeBefore.Next = newNode;
      end

이중 연결 리스트에서 지정된 노드 다음에 노드를 삽입하거나 리스트가 아직 없는 경우 두 개의 지정된 노드를 서로 연결합니다. Next 속성과 Prev 속성에 대한 올바른 값을 할당합니다.

노드 삽입하기 

      function insertBefore(newNode, nodeAfter)
         removeNode(newNode);
         newNode.Next = nodeAfter;
         newNode.Prev = nodeAfter.Prev;
         if ~isempty(nodeAfter.Prev)
            nodeAfter.Prev.Next = newNode;
         end
         nodeAfter.Prev = newNode;
      end

이중 연결 리스트에서 지정된 노드 앞에 노드를 삽입하거나 리스트가 아직 없는 경우 두 개의 지정된 노드를 서로 연결합니다. 이 메서드는 Next 속성과 Prev 속성에 대한 올바른 값을 할당합니다.

노드 삽입하기 항목을 참조하십시오.

      function removeNode(node)
         if ~isscalar(node)
            error('Nodes must be scalar')
         end
         prevNode = node.Prev;
         nextNode = node.Next;
         if ~isempty(prevNode)
            prevNode.Next = nextNode;
         end
         if ~isempty(nextNode)
            nextNode.Prev = prevNode;
         end
         node.Next =  = dlnode.empty;
         node.Prev =  = dlnode.empty;
      end

나머지 노드가 올바르게 연결되도록 노드를 제거하고 리스트를 수정합니다. node 인수는 스칼라여야 합니다.

노드에 대한 참조가 없으면 MATLAB이 노드를 삭제합니다.

노드 제거하기 

      function clearList(node)
         prev = node.Prev;
         next = node.Next;
         removeNode(node)
         while ~isempty(next)
            node = next;
            next = node.Next;
            removeNode(node);
         end
         while ~isempty(prev)
            node = prev;
            prev = node.Prev;
            removeNode(node)
         end
      end

리스트 변수를 지운 결과로 소멸자에 대한 재귀적 호출이 수행되지 않도록 합니다. 리스트를 순환하며 각 노드의 연결을 끊습니다. 노드에 대한 참조가 없으면 MATLAB이 클래스 소멸자를 호출한 후(delete 메서드 참조) 노드를 삭제합니다.

   methods (Access = private)
      function delete(node)
         clearList(node)
      end

클래스 소멸자 메서드입니다. 리스트에 아직 연결되어 있는 노드를 삭제하면 MATLAB이 delete 메서드를 호출합니다. 

   end
end

프라이빗 메서드의 끝이고 클래스 정의의 끝입니다.

 확장하여 클래스 코드 보기

클래스 속성

Next 속성과 Prev 속성은 프라이빗 set 액세스(SetAccess = private)를 가지므로 dlnode 클래스 메서드만 이들 속성을 설정할 수 있습니다. 프라이빗 set 액세스를 사용하면 클라이언트 코드가 이들 속성으로 잘못된 연산을 수행하지 않도록 방지됩니다. dlnode 클래스 메서드는 이 노드에 대해 허용되는 연산을 모두 수행합니다.

Data 속성은 퍼블릭 set 액세스 및 get 액세스를 가지므로 이를 통해 필요에 따라 Data의 값을 쿼리하고 수정할 수 있습니다.

dlnode 클래스가 속성을 정의하는 방법은 다음과 같습니다.

properties
   Data
end
properties(SetAccess = private)
   Next = dlnode.empty;
   Prev = dlnode.empty;
end

노드 객체 생성하기

노드 객체를 생성하려면 노드의 데이터를 생성자에 대한 인수로 지정하십시오.

function node = dlnode(Data)
   if nargin > 0
      node.Data = Data;
   end
end

노드 삽입하기

노드를 리스트에 삽입할 수 있는 메서드는 insertAfter와 insertBefore, 두 가지가 있습니다. 이 두 메서드는 유사한 작업을 수행하므로 이 섹션에서는 insertAfter에 대해서만 자세히 설명합니다.

function insertAfter(newNode, nodeBefore)
   removeNode(newNode);
   newNode.Next = nodeBefore.Next;
   newNode.Prev = nodeBefore;
   if ~isempty(nodeBefore.Next)
      nodeBefore.Next.Prev = newNode;
   end
   nodeBefore.Next = newNode;
end

insertAfter 작동 방식.  먼저, insertAfter는 removeNode 메서드를 호출하여 새 노드가 다른 노드에 연결되어 있지 않도록 합니다. 그런 다음, insertAfter가 newNode의 Next 속성과 Prev 속성을 리스트에서 newNode 자리의 앞과 뒤에 있는 노드의 핸들에 할당합니다.

예를 들어, n1—n2—n3이 있는 리스트에서 기존 노드 n1 다음에 새 노드 nnew를 삽입한다고 가정하겠습니다.

먼저, nnew를 생성합니다.

nnew = dlnode(rand(3));

그런 다음, insertAfter를 호출하여 리스트에서 n1 다음에 nnew를 삽입합니다.

nnew.insertAfter(n1)

insertAfter 메서드는 다음과 같은 단계를 수행하여 리스트에서 n1과 n2 사이에 nnew를 삽입합니다.

  • nnew.Next를 n1.Next(n1.Next는 n2임)로 설정합니다.

    nnew.Next = n1.Next;

  • nnew.Prev를 n1로 설정합니다.

    nnew.Prev = n1;

  • n1.Next가 비어 있지 않을 경우 n1.Next는 여전히 n2이므로 n1.Next.Prev는 nnew로 설정되는 n2.Prev가 됩니다.

    n1.Next.Prev = nnew;

  • 이제 n1.Next가 nnew로 설정되었습니다.

    n1.Next = nnew;

New node inserted into doubly linked list

노드 제거하기

removeNode 메서드는 리스트에서 노드를 제거하고 나머지 노드를 다시 연결합니다. insertBefore 메서드와 insertAfter 메서드는 연결 리스트에 연결하기 전에 항상 삽입할 노드에 대해 removeNode를 호출합니다.

removeNode를 호출하면 노드를 Next 속성 또는 Prev 속성에 할당하기 전에 노드가 알려진 상태가 되도록 합니다.

function removeNode(node)
   if ~isscalar(node)
      error('Input must be scalar')
   end
   prevNode = node.Prev;
   nextNode = node.Next;
   if ~isempty(prevNode)
      prevNode.Next = nextNode;
   end
   if ~isempty(nextNode)
      nextNode.Prev = prevNode;
   end
   node.Next = dlnode.empty;
   node.Prev = dlnode.empty;
end

예를 들어, 세 개의 노드로 구성된 리스트(n1–n2–n3)에서 n2를 제거한다고 가정하겠습니다.

n2.removeNode;

Disconnecting links after removing a node from doubly linked list

removeNode는 다음 단계를 통해 리스트에서 n2를 제거하고 나머지 노드를 다시 연결합니다.

n1 = n2.Prev;
n3 = n2.Next;
if n1 exists, then
   n1.Next = n3;
if n3 exists, then
   n3.Prev = n1

n1이 n3에 연결되고 n3이 n1에 연결되므로 리스트가 다시 연결됩니다. 최종 단계는 n2.Next와 n2.Prev 모두 비어 있도록 하는 것입니다(즉, n2가 연결되어 있지 않음).

n2.Next = dlnode.empty;
n2.Prev = dlnode.empty;

리스트에서 노드 제거하기

10개 노드로 구성된 리스트를 생성하고 핸들을 리스트의 헤드(처음 노드)에 저장한다고 가정하겠습니다.

head = dlnode(1);
for i = 10:-1:2
   new = dlnode(i);
   insertAfter(new,head);
end

이제, 세 번째 노드(값 3이 할당된 Data 속성)를 제거합니다.

removeNode(head.Next.Next)

이제 리스트에서 세 번째 노드의 데이터 값이 4입니다.

head.Next.Next

ans = 

  dlnode with properties:

    Data: 4
    Next: [1x1 dlnode]
    Prev: [1x1 dlnode]

그리고 이전 노드의 Data 값은 2입니다.

head.Next

ans = 

  dlnode with properties:

    Data: 2
    Next: [1x1 dlnode]
    Prev: [1x1 dlnode]

노드 삭제하기

노드를 삭제하려면 해당 노드에 대해 removeNode 메서드를 호출하십시오. removeNode 메서드는 MATLAB이 제거된 노드를 소멸시키도록 허용하기 전에 노드의 연결을 끊고 리스트를 다시 연결합니다. MATLAB은 다른 노드에 의한 노드 참조가 제거되고 리스트가 다시 연결되면 이 노드를 소멸시킵니다.

Reconnecting links after deleting node from doubly linked list

리스트 삭제하기

연결 리스트를 생성하고 리스트의 헤드(처음 노드) 또는 테일(끝 노드)을 포함하는 변수를 할당할 경우 해당 변수를 지우면 소멸자가 전체 리스트를 재귀적으로 순회하게 됩니다. 충분히 큰 리스트에서 리스트 변수를 지우면 MATLAB이 재귀 제한값을 초과하게 될 수 있습니다.

clearList 메서드는 리스트를 순회하며 각 노드의 연결을 끊어 재귀를 방지하고 대규모 리스트 삭제 성능을 향상시킵니다. clearList는 리스트에서 임의 노드의 핸들을 받고 나머지 노드를 제거합니다.

function clearList(node)
   if ~isscalar(node)
      error('Input must be scalar')
   end
   prev = node.Prev;
   next = node.Next;
   removeNode(node)
   while ~isempty(next)
      node = next;
      next = node.Next;
      removeNode(node);
   end
   while ~isempty(prev)
      node = prev;
      prev = node.Prev;
      removeNode(node)
   end
end

예를 들어, 노드가 많은 리스트를 생성한다고 가정하겠습니다.

head = dlnode(1);
for k = 100000:-1:2
   nextNode = dlnode(k);
   insertAfter(nextNode,head)
end

변수 head에는 리스트의 헤드에 있는 노드에 대한 핸들이 포함되어 있습니다.

head
head = 

  dlnode with properties:

    Data: 1
    Next: [1x1 dlnode]
    Prev: []
head.Next
ans = 

  dlnode with properties:

    Data: 2
    Next: [1x1 dlnode]
    Prev: [1x1 dlnode]

clearList를 호출하여 리스트 전체를 제거할 수 있습니다.

clearList(head)

MATLAB에 의해 삭제되지 않은 노드는 명시적 참조가 존재하는 노드 뿐입니다. 이 경우에는, 명시적 참조는 head와 nextNode입니다.

head
head = 

  dlnode with properties:

    Data: 1
    Next: []
    Prev: []

nextNode
nextNode = 

  dlnode with properties:

    Data: 2
    Next: []
    Prev: []

변수를 지워서 이러한 노드를 제거할 수 있습니다.

clear head nextNode

delete 메서드

delete 메서드는 단순히 clearList 메서드를 호출합니다.

methods (Access = private)
   function delete(node)
      clearList(node)
   end
end

delete 메서드는 프라이빗 액세스를 가지므로 사용자가 단일 노드를 삭제하려고 할 때 delete를 호출하지 못하도록 합니다. MATLAB은 리스트가 소멸되면 delete를 묵시적으로 호출합니다.

리스트에서 단일 노드를 삭제하려면 removeNode 메서드를 사용하십시오.

dlnode 클래스 특화하기

dlnode 클래스는 이중 연결 리스트를 구현하고 더욱 특화된 유형의 연결 리스트를 편리하게 생성할 수 있는 시작점이 됩니다. 예를 들어, 노드마다 이름이 하나씩 있는 리스트를 생성한다고 가정하겠습니다.

dlnode 클래스를 구현하는 데 사용한 코드를 복사한 후 이를 바탕으로 확장하는 대신 dlnode(즉, 서브클래스 dlnode)에서 새 클래스를 파생할 수 있습니다. 사용자는 dlnode의 모든 특징을 가지며 자체적으로 추가적인 특징도 정의하는 클래스를 생성할 수 있습니다. dlnode는 핸들 클래스이므로 이 새 클래스도 핸들 클래스입니다.

NamedNode 클래스 정의

이 클래스를 사용하려면 이름이 @NamedNode인 폴더를 생성하고 NamedNode.m을 이 폴더에 저장하십시오. @NamedNode의 부모 폴더는 MATLAB 경로에 있어야 합니다. 또는, NamedNode.m을 경로 폴더에 저장하십시오.

다음 클래스 정의는 dlnode 클래스에서 NamedNode 클래스를 파생하는 방법을 보여줍니다.

classdef NamedNode < dlnode
   properties
      Name = ''
   end
   methods
      function n = NamedNode (name,data)
         if nargin == 0
            name = '';
            data = [];
         end
         n = n@dlnode(data);
         n.Name = name;
      end
   end
end

NamedNode 클래스는 노드 이름을 저장하는 Name 속성을 추가합니다.

생성자는 dlnode 클래스에 대한 클래스 생성자를 호출한 후 Name 속성에 값을 할당합니다.

NamedNode를 사용하여 이중 연결 리스트 생성하기

dlnode 클래스처럼 NamedNode 클래스를 사용하되, 각 노드 객체에 이름을 지정합니다. 예를 들면 다음과 같습니다. 

n(1) = NamedNode('First Node',100);
n(2) = NamedNode('Second Node',200);
n(3) = NamedNode('Third Node',300);

이제, dlnode에서 상속된 insert 메서드를 사용하여 리스트를 만듭니다.

n(2).insertAfter(n(1))
n(3).insertAfter(n(2))

단일 노드의 속성을 쿼리하면 해당 노드의 이름과 데이터가 표시됩니다.

n(1).Next
ans = 

  NamedNode with properties:

    Name: 'Second Node'
    Data: 200
    Next: [1x1 NamedNode]
    Prev: [1x1 NamedNode]
n(1).Next.Next
ans = 

  NamedNode with properties:

    Name: 'Third Node'
    Data: 300
    Next: []
    Prev: [1x1 NamedNode]
n(3).Prev.Prev
ans = 

  NamedNode with properties:

    Name: 'First Node'
    Data: 100
    Next: [1x1 NamedNode]
    Prev: []

관련 항목