CSDataStructure

[자료구조] 연결 리스트(Linked List)

CS, DataStructure

연결 리스트(Linked List)

Linked List란, 원소 간의 연결(link)을 이용해서 리스트를 구현한 것이다.

이전 포스트에서 설명한 Array List는 논리적인 순서와 물리적인 순서가 같기 때문에 원소의 위치를 찾아 접근하기 쉽다는 장점이 있지만, 삽입이나 삭제 후에 연속적인 물리 주소를 유지하기 위해서 원소들을 이동시키는 추가적인 작업과 시간이 필요하다. 하지만 연결 리스트는 리스트를 연결 자료구조 방식으로 표현한 구조로서, 원소들끼리 연결되어 있기 때문에 삽입이나 삭제를 할 때 연결만 달리 해주면 된다. 따라서 원소들을 이동시키는 추가적인 작업이 필요하지 않다.


노드

연결 자료구조 방식에서 원소는 연결될 다음 원소에 대한 주소를 저장해야 하기 때문에 <원소, 주소>의 단위로 저장해야 한다. 이러한 단위 구조를 노드(node)라고 한다. 각각의 노드가 다음 노드의 주소를 알고 있기 때문에 하나의 연결된 값의 모임을 만들 수 있는 것이다.


연결 리스트 삽입

1) 리스트의 맨 앞에 노드 삽입

  • ① new <- getNode() : 삽입할 노드를 자유 공간 리스트에서 할당받는다.
  • ② new.data <- x : 새 노드의 데이터 필드에 x를 저장한다.
  • ③ new.link <- L : 리스트 L의 첫 번째 노드에 대한 참조값을 삽입할 새 노드 new의 링크 필드에 저장함으로써 새 노드 new를 리스트 L의 첫 번째 노드와 연결한다.
  • ④ L <- new : 참조변수 L에 새 노드에 대한 참조값700을 저장하여 L이 새 노드 new를 첫 번째 노드로 가리키도록 지정한다.
1
2
3
4
5
6
insertFirstNode(L, x)
    new <- getNode();
    new.data <- x;
    new.link <- L;
    L <- new;
end insertFirstNode();


2) 리스트의 중간에 노드 삽입

  • ① new.link <- pre.link : 참조변수 pre는 삽입할 위치의 앞 노드를 가리킨다. 따라서 pre가 가리키는 노드의 다음 노드로 새 노드 new를 연결해야 하므로 노드 pre의 링크 필드값200을 노드 new의 링크 필드에 저장하여, 새 노드new가 노드 pre의 다음 노드를 가리키게 한다.
  • ② pre.link <- new : new의 주소700을 노드 pre의 링크 필드에 저장하여 pre가 가리키는 노드의 다음 노드로서 새 노드 new를 연결한다.
1
2
3
4
5
6
7
8
9
10
11
insertMiddleNode(L, pre, x)
    new <- getNode();
    new.data <- x;
    if (L = null) then {
        L <- new;
        new.link <- null;
    } else {
        new.link <- pre.link;
        pre.link <- new;
    }
end insertMiddleNode()


3) 리스트의 마지막에 노드 삽입

temp를 사용해서 가장 마지막 노드가 무엇인지 찾고, 가장 마지막 노드의 링크 필드값에 new의 주소700을 저장하여 가장 마지막 노드가 새 노드 new를 가리키게 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
insertLastNode(L, x)
    new <- getNode();
    new.data <- x;
    new.link <- null;
    if (L = null) then {
        L <- new;
        return;
    }
    temp <- L;
    while (temp.link != null) do
        temp <- temp.link;
    temp.link <- new;
end insertLastNode()


연결 리스트 삭제

삭제할 노드를 가리키는 참조변수 old와 삭제할 노드의 바로 앞의 노드를 가리키는 참조변수 pre를 이용하여 노드를 하나 삭제할 수 있다.

  • ① old <- pre.link : old는 삭제할 노드를 지시해야 하므로 노드 pre의 링크 필드값을 저장한다.
  • ② pre.link <- old.link : 삭제할 노드 old의 다음 노드를 노드 pre의 다음 노드로 연결한다.
1
2
3
4
5
6
7
8
9
deleteNode(L, pre)
    if (L = null) then error;
    else {
        old <- pre.link;
        if (old = null) then return;
        pre.link <- old.link;
    }
    returnNode(old);
end deleteNode()


추가

자료구조 List 시각화 사이트를 참고하여 리스트에 대해 확실히 알아두자.

Share