연결 리스트 (Linked List)
선형 데이터 구조
- 데이터 와, 그 뒤의 데이터는 1:1 관계이다. 즉 1개의 데이터 뒤에는 1개의 데이터만 존재한다.
- 리스트의 끝, 혹은 특정 데이터에 도달하려면 리스트의 모든 항목을 순차적으로 거쳐야 한다.
- 반면, 비선형 데이터 구조에서는 항목들이 순서대로 배열될 필요가 없어 비순차적으로 데이터 구조를 순회할 수 있다.
동적 데이터 구조
동적 데이터 구조는 메모리에서 축소되거나 확장될 수 있다. 존재하기 위해 정해진 양의 메모리가 할당될 필요가 없으며, 크기와 모양이 변할 수 있고 필요한 메모리의 양도 변할 수 있다.
구성 요소
연결 리스트는 일련의 노드로 구성된다. 단순히 말해, 그저 노드들의 모음이라고 볼 수 있다. 데이터와, 그 다음 데이터를 가리키는 포인터로 이루어져 있다.
헤드 : 연결 리스트의 시작점으로써, 첫 번째 노드에 대한 참조이다. 거의 모든 연결 리스트에는 헤드 가 있어야 한다. 이는 실질적으로 리스트와 모든 요소에 대한 유일한 진입점이기 때문. 노드 : 헤드 와 마지막 노드를 제외한 노드들로써, 데이터와 그 다음 데이터를 가리키는 포인터로 이루어져있다. 마지막 노드 : 노드가 아니라 null 또는 빈 값을 가리키는 노드입니다.
노드 의 작동 방식
노드는 자신이 포함하는 데이터와, 그 다음 노드가 누구인지만 알고 있다.
연결 리스트가 연속적인 메모리 블록에 할당될 필요가 없는 이유를 설명한다. 노드는 다음 노드에 대한 참조인 포인터를 가지고 있기 때문에, 물리적으로 붙어있을 필요없이 떨어져 있을 수 있는 것이다.
구성 방식
단일 연결 리스트
한 방향으로만 진행되는 기본적인 형태의 연결 리스트를 의미한다. 헤드에서 출발하여 마지막 노드 까지 한 방향으로만 진행한다.
이중 연결 리스트
이전 노드에 대한 참조 포인터를 가져, 두 방향으로 진행될 수 있는 연결 리스트를 의미한다.
따라서 노드는 다음 노드, 이전 노드 에 대한 포인터를 가진다. 이는 데이터 구조를 한가지 방향이 아닌 반대로도 순회할 수 있게 하고자 할 때 유용할 수 있다.
예를 들어, 리스트의 현재 노드 에서, 3개 전의 노드로 이동하고 싶을 때, 이중 연결 리스트를 사용하면 맨 처음으로 돌아가지 않고도 이동할 수 있다.
원형 연결 리스트
마지막 노드가 null 값을 가리키며 끝나지 않고, 헤드가 가리키는 노드를 가리키는 형태의 연결 리스트를 의미한다. 여기서 마지막 노드를 tail 이라고도 부른기도 한다.
이중 연결리스트와 마찬가지로 하나의 노드에서 다른 모든 노드로의 접근이 가능하다. 노드의 삽입, 삭제가 단순 / 이중 연결 리스트 보다 용이하다.
배열 과의 유사성과 차이점
데이터 순서화 방식
배열 또한 선형 데이터 구조를 사용하기에, 데이터를 순차적으로 거쳐야하는 점에서 배열과 연결 리스트는 유사 하다고 볼 수 있다.
메모리 관리
배열과 연결 리스트의 가장 큰 차이점은 기계 수준에서 메모리를 사용하는 방식이다.
배열의 메모리 관리
예를 들어, 7개의 문자를 각각 배열과 연결 리스트에 저장해야 한다고 치자. 그렇다면 7바이트의 메모리를 저장할 공간이 필요할 것이다.
배열은 모든 7바이트의 메모리가 연속된 블록에 있어야 한다. 즉, 컴퓨터는 한 곳에, 서로 옆에 붙어있는 상태의 7바이트의 메모리를 찾아야 한다.
이러한 특성은, index 로 특정 데이터에 접근할 수 있다는 점에서 데이터에 접근하고 조회하는 속도가 빠르다는 장점이 있다.
하지만 마찬가지로 이러한 특성 때문에, 데이터를 중간에 삽입 혹은 삭제할 때 단점이 된다. 연속적인 블록의 구조를 갖춰야하기에, 중간에 데이터가 삽입 혹은 삭제되면 그만큼 데이터를 이동해야하기 때문이다.
연결 리스트의 메모리 관리
반면에 연결 리스트가 생성될 때는 7바이트의 메모리가 한 곳에 있을 필요가 없다. 한 바이트는 어딘가에 있고, 다음 바이트는 메모리의 완전히 다른 곳에 저장될 수 있다.
각 노드는 다음 노드에 대한 정보들 밖에 없기 때문에, 특정 데이터에 접근하려면 모두 순회해야하기에 배열보다 시간이 오래걸린다는 단점이 있다.
반대로 데이터를 삽입 혹은 삭제할때 배열과 같이 연속적인 블록 형태를 유지할 필요가 없기에, 유연하게 가능하다.
메모리 할당 방식
배열은 정적, 연결 리스트는 동적 데이터 구조를 가진다.
정적 데이터 구조는 구조가 생성될 때 크기와 메모리 양을 정한다. 따라서 구조의 크기가 커지거나 작아지고 요소가 추가되거나 제거되더라도 항상 주어진 크기와 메모리 양이 필요하게 된다.
만약, 정적 데이터 구조에 더 많은 요소를 추가해야 하는데 메모리가 충분하지 않다면, 데이터를 복사하고 더 많은 메모리로 재생성하여 요소를 추가해야 한다.
반면 동적 데이터 구조는 앞서 살펴봤듯, 구조가 생성될때 크기와 메모리 양을 정할 필요 없다. 따라서 더 많은 요소를 추가하거나 제거하더라도, 메모리는 축소 혹은 확장될 수 있다.
가상 메모리 구현
일부 운영체제에서는 가상 메모리 의 프레임을 관리할때, 연결 리스트를 사용하기도 한다. 가상 메모리 시스템에서는 프레임에 대한 할당과 삭제가 빈번하기 일어나기에, 구조 중간의 데이터를 삽입 및 삭제에 용이한 연결 리스트를 사용한다.
