자료 구조 - 단일 연결 리스트 Singly Linked List, 파이썬으로 구현한 단일 연결 리스트 예제

연결 리스트Linked List란?

각 노드(node)가 데이터와 포인터를 가지고 한 줄로 연결된 자료 구조.

참고: 위키백과 연결 리스트

 

그렇다면 노드란?

단일 연결 리스트 예 (출처: 위키백과)

위 그림에서 네모 두 칸이 노드다. 12가 데이터, 다른 노드를 가리키고 있는 화살표가 바로 포인터다.

 

파이썬 노드 코드 예

 

노드를 한 줄로 연결하게 되면 연결 리스트가 된다.

연결 리스트 중 포인터가 하나인 경우가 단일 연결 리스트이다.

 

단일 연결 리스트 파이썬 구현 예

아래는 파이썬으로 구현한 단일 연결 리스트 예이다.

 

 

 

 

앞에서 살펴본 스택이나 큐보다 훨씬 복잡하다.

노드란 객체를 만들어서 연결하기 때문에 더 복잡해 보인다.

코드를 이해하기 위해서는 천천히 살펴볼 필요가 있다.

 

그렇다면 왜 연결 리스트를 사용할까?

많은 프로그래밍 언어에서 배열이란 자료형을 사용할 경우, 배열 크기를 미리 정의하고 사용한다. 자바 코드를 예로 들면 아래와 같다.

class Main {
    public static void main(String[] args) {
        int[] arr = new int[3];
        arr[0] = 1;
        arr[1] = 2;
        arr[2] = 3;
        System.out.println(arr[0]);
        System.out.println(arr[1]);
        System.out.println(arr[2]);
        System.out.println(arr);
    }
}

위 코드에서 new int[3]으로 int 타입 배열로 크기는 3을 선언하고 사용하게 된다. 값 4개는 저장할 수 없다.

만약 크기가 4이고 값이 {1, 2, 3}인 배열에 1과 2 사이에 0을 넣게 된다면, {1, 0, 2, 3}으로 2와 3의 값을 다음 칸으로 옮겨야 하는 번거로움이 생긴다.

연결 리스트로 구현하면 크기를 제한 없이 늘릴 수 있다. 또 중간에 임의로 쉽게 데이터를 넣을 수 있게 된다.

 

파이썬의 리스트는 배열일까? 아니면 연결 리스트일까?

nums = []
nums.append(1)
nums.append(2)
nums.append(3)
print(nums[0])
print(id(nums[0]))
print(nums[1])
print(id(nums[1]))
print(nums[2])
print(id(nums[2]))

nums.insert(1, 10)
print(nums)

print(nums[0])
print(id(nums[0]))
print(nums[1])
print(id(nums[1]))
print(nums[2])
print(id(nums[2]))
print(nums[3])
print(id(nums[3]))

출력 결과

1
4447828320
2
4447828352
3
4447828384
[1, 10, 2, 3]
1
4447828320
10
4447828608
2
4447828352
3
4447828384

위 출력 결과를 보면 10만 주소값이 뛴 것을 볼 수 있고, 2와 3의 주소값은 그대로인 것을 알 수 있다. 파이썬 리스트 자체가 연결 리스트로 구현되어 있다고 추정할 수 있다.