연결리스트

동적으로 크기가 변할 수 있고 삭제나 삽입 시에 데이터를 이동할 필요가 없는 연결된 표현(Linked representation) 에 대해 알아보겠다. 이 연결된 표현은 포인터를 사용하여 데이터들을 연결한다. 연결된 표현은 널리 사용되며 추상 데이터 타입 "리스트" 의 구현에만 사용되는 것이 아니고 다른 여러가지의 자료구조(트리, 그래프, 스택, 큐) 등을 구현하는데도 많이 사용된다.

이렇게 연결된 표현은 줄로 연결된 상자라고 생각할 수 있다. 상자 안에는 데이터가 들어가고 상자에 연결된 줄을 따라가면 다음 상자를 찾을 수 있다. 연결된 표현은 일단 데이터를 한군데 모아두는 것을 포기하는 것이다. 데이터들은 메인 메모리상의 어디에나 흩어져서 존재할 수 있고 이런 자료들을 서로 연결하여 하나로 묶는 방법을 연결 리스트(Linked list) 라고 한다. 상자를 연결하는 줄은 포인터(pointer) 로 구현한다.

 

연결리스트를 사용하면 배열을 이용한 리스트에서 가장 문제가 되었던 중간에 삽입하는 문제를 해결할 수 있다. 연결 리스트에서는 앞뒤에 있는 데이터들을 이동할 필요가 없이 줄만 변경시켜주면 된다. 삭제 시에도 마찬가지로 데이터들을 연결하는 줄만 수정하면 된다. 

하나의 프로그램 안에는 동시에 여러 개의 연결 리스트가 존재한다. 이런 경우 연결리스트를 구별하는 것은 첫 번째 데이터이다. 첫 번째 데이터만 알 수 있으면 연결 리스트의 나머지 데이터들은 줄만 따라가면 얻을 수 있다. 연결 리스트의 또 하나의 장점은 데이터를 저장할 공간이 필요할 때마다 동적으로 공간을 만들어서 쉽게 추가할 수 있다는 것이다. 이것은 순차적인 표현 방법인 배열에 비하여 상당한 장점이 된다.

 그러나 장점만 있는 것은 아니고 배열에 비하여 상대적으로 구현이 어렵고 오류가 나기 쉬운 점은 단점이라고 할 수 있다. 또 데이터 뿐만 아니라 포인터도 저장하여야 하므로 메모리 공간을 많이 사용한다. 또 i번째 데이터를 찾으려면 앞에서부터 순차적으로 접근하여야 한다.

 

 

우리는 이제 상자 상자를 컴퓨터 용어로 노드(node) 라고 부를 것이다. 연결 리스트는 이들 노드들의 집합이다. 노드들은 메모리의 어떤 위치에나 있을 수 있으며 다른 노드로 가기 위해서는 현재 노드가 가지고 있는 포인터를 이용하면 된다. 노드는 데이터 필드(data field) 와 링크 필드(link field) 로 구성되어 있다.

데이터 필드에는 우리가 저장하고 싶은 데이터가 들어간다. 데이터는 정수가 될 수도 있고 구조체와 같은 복잡한 데이터가 될 수도 있다. 링크 필드에는 다른 노드를 가리키는 포인터가 저장된다. 이 포인터를 이용해야 다음 노드로 건너갈 수 있다. 연결 리스트에서는 연결 리스트의 첫번째 노드를 알아야만이 전체의 노드에 접근할 수 있다. 따라서 연결 리스트마다 첫 번째 노드를 가리키고 있는 변수가 필요한데 이것을 헤드 포인터(head pointer) 라고 한다. 그리고 마지막 노드의 링크 필드는 NULL 으로 설정되는데 이는 더 이상 연결된 노드가 없다는 것을 의미한다. 연결 리스트의 노드들은 필요할 때마다 malloc() 을 이용하여 동적으로 생성된다.