[자료구조 및 프로그래밍] 4. Linked List

지난 글까지 Array 를 이용한 스택과 큐의 구현에 대해 정리하였고, 지난 글에서는 특히 단순하게 구현한 큐에서 메모리를 제대로 활용하지 못하는 문제를 해결하기 위해 Circular Queue 를 구현하는 과정을 소개하였다.

 

이번 글에서는 Array 와 다른 Linked List 라는 새로운 자료구조를 정리하고자 한다.

---

Linked List

Linked List 는 한국어로 번역하면 '연결리스트' 라고 한다.

말 그대로 선으로 연결하여 나타낸 리스트를 의미하는데, 연결 리스트의 특징은 배열과 달리 데이터와 데이터가 메모리의 연속된 공간에 존재하지 않을 수 있다.

대신 연결된 다음 데이터를 나타낼 그 데이터의 주소를 같이 저장함으로서 데이터와 데이터의 연결관계를 나타내는 특징이 있다.

 

그림과 같이 저장할 '데이터' 와 다음에 연결된 '데이터의 주소' 를 같이 담고 있는 연결 리스트 내 단위 요소를 '노드' 라고 한다.

 

노드에는 데이터가 담겨있는 ITEM  파트와, 연결된 다음 노드의 메모리 주소가 담겨있는 LINK 파트가 있다.

연결리스트를 나타낼 때는 아래와 같이 선으로 각 노드를 연결하여 나타낸다.

연결 리스트에 접근하기 위해서는 첫 번째 노드에 접근하기 위한 첫 번째 노드의 주소가 필요하고,

마지막 노드의 경우 연결된 링크가 없기 때문에 연결된 링크를 Null 로 설정하는 초기화 과정이 필요하다.

마지막 노드에 연결된 링크가 없는 것을, '접지' 라고 표현하며, 이 곳에 들어있는 데이터를 그리스 대문자 람다 ( ^ 모양)로 표현한다.

---

연결 리스트와 배열의 비교

 

1. 연결된 노드의 메모리 위치를 저장할 추가적인 메모리 공간이 필요하다.

2. 배열과 달리 데이터를 중간에 삽입하고, 중간 데이터를 삭제하는 것이 간단하다.

(배열은 데이터를 중간에 추가하거나 삭제하면 나머지 데이터를 옮겨주는 과정이 필요하다.)

3. 배열은 인덱스를 이용해 원하는 위치에 바로 직접 접근이 가능하지만 (Random Access)

링크드 리스트는 원하는 위치에 바로 접근할 수 없어 첫번째 노드부터 카운팅하며 쭉 따라가 접근해야 한다. (Marching Down)

4. 서로 다른 두 연결리스트를 합쳐 하나의 연결리스트로 만드는 과정이 간단하다.

(배열은 그 두 배열의 사이즈 합에 해당하는 배열을 새로 선언하고 두 배열의 값을 복사해 다시 넣어야한다.)

5. 메모리를 할당할 때, '연속된' 메모리 덩어리가 필요하지 않기 때문에, 메모리 활용이 효율적이다.

(배열은 처음 선언할 때, '연속된' 큰 덩어리 메모리가 필요하지만, 연결리스트는 하나의 노드를 생성할 작은 덩어리 메모리만 있으면 된다.)

---

연결리스트의 순회

연결리스트를 순회할 때는 현재 순회중인 노드를 가리킬 보조 변수가 필요하다.

첫 노드를 가리키는 변수를 l 이라고 할 때 아래와 같이 순회할 수 있다.

l: the first node address

p <- l
while (p != null) {
    print(ITEM(p))
    p <- LINK(p)
}

// ITEM(p) : p 가 가리키는 노드의 ITEM 부분
// LINK(p) : p 가 가리키는 노드의 LINK 부분

데이터 삽입

데이터 삽입 시 새로운 노드를 생성해야 하는데, 이 함수로 new() 라는 함수가 있다고 가정해보자.

추후 연결리스트 메모리 관리 시스템에 대해 정리할 때, new 함수를 직접 구현해 볼 것이다.

 

데이터를 삽입할 때는 새로운 노드로 쓸 메모리를 할당받는다.

C언어의 malloc 함수와 마찬가지로, 메모리를 할당받는데 성공하면, 그 메모리의 주소를 얻고, 실패하면 NULL 을 얻는다.

 

이제 새로 생성한 노드의 ITEM 부분을 채우고,

데이터를 삽입할 위치의 이전 노드의 LINK 부분을 새로 할당받은 메모리의 주소로 채우고,

데이터를 삽입할 위치의 이전 노드의 LINK 부분에 있던 그 다음 노드를 새로 할당받은 노드의 LINK 부분으로 채우면 연결관계 설정이 끝난다.

 

이를 코드로 정리하면 아래와 같다.

p: previous node
q: new node

q <- new()
if (q == NULL)
    OVERFLOW!
    
ITEM(q) <- DATA
LINK(q) <- LINK(p)
LINK(p) <- q

주소를 설정할 때, LINK(q) <- LINK(p) 를 먼저 해야하는 것을 유의하면 어렵지 않다.

데이터 삭제

데이터를 삭제할 때는, 삭제할 위치의 노드 주소와, 그 이전 노드 주소가 필요하다.

이전 노드 주소가 필요한 이유는 노드를 삭제한 이후 연결관계를 다시 설정하기 위함이다.

또 노드의 메모리를 반환하기 위한 free() 함수가 존재한다고 가정해보자.

 

데이터 삭제 과정을 글로 정리하면 아래와 같다.

우선 삭제할 노드를 traverse 하여 찾는다.

이때 traverse 하면서 현재 방문한 노드와 그 이전 노드를 같이 저장하며 순회해야한다.

 

삭제할 노드를 찾았다면, 아래와 같이 노드를 삭제한다.

우선 이전 노드의 LINK 부분을 삭제할 노드가 가리키고 있던 LINK 로 바꿔주고,

이제 연결관계가 끊어졌으니 삭제할 노드의 메모리를 반환한다.

 

이를 코드로 정리하면 아래와 같이 된다.

p: 삭제할 노드의 이전 노드
q: 삭제할 노드

LINK(p) <- LINK(q)
free(q)

연결 관계만 재설정하고, 이전 노드의 할당을 풀어주는 것이므로 아주 간단하게 구현된다.

---

지금까지 연결리스트와, 연결리스트의 데이터 순회, 삽입, 삭제 구현 방법에 대해 정리하였다.

다음 글에서는 연결리스트를 이용해 스택과 큐를 구현하는 방법을 정리해 보고자한다.