연결 리스트의 개념
최종 수정 : 24.12.27
연결 리스트의 개념
1. 연결 리스트의 필요성
배열은 순서 리스트로 기억공간에 연속적으로 저장되므로 논리적인 순서와 물리적인 순서가 같아서 원소들을 찾아 접근하기 쉬우나 삽입과 삭제 연산에서 속도와 성능이 떨어지는 문제가 있다. 이런 문제들을 해결하기 위해 연결 리스트(linked list)라는 구조가 있다.
연결리스트는 연속적인 기억공간을 필요하지 않은 리스트로, 기본단위인 노드(Node)라는 것을 포인트(point)를 이용하여 체인과 같이 연결된 구조이다. 이 구조를 통해 순서 리스트와 단점인 삽입과 삭제의 문제를 해결할 수 있다. 기억공간의 여러 곳에 흩어져 존재할 수 있어 물리적으로 연속된 기억공간을 요구하지 않는다.
2. 연결 리스트의 개념
노드는 데이터와 링크로 구성되어 있다. 연결 리스트의 종류는 단순 연결 리스트, 환형 연결 리스트, 이중 연결 리스트, 환형 이중 연결 리스트가 있다.
1) 연결 리스트의 장단점
장점
- 노드의 삽입&삭제가 용이하다.
- 연속적으로 기억 공간이 없어도 저장이 가능하다.
단점
- 순서 리스트나 배열보다 기억 공간이 많이 필요하다.
- 알고리즘 구현이 복잡하다.
- 특정 노드 검색 시 무한 루프에 빠질 수 있다.
3. 노드의 구조
연결 리스트의 기본 구조는 노드(Node)라고 불리는 원소들을 서로 연결해 놓은 리스트이다. 노드는 데이터(data)와 링크(link)로 구성되며, 링크는 다음 노드의 주소(address 또는 포인터(pointer))를 가지고 있다.
| data | link | ---> | data | link | ---> | data | link |
- 데이터 부분
☞저장되는 데이터의 값을 나타내며, 저장할 원소의 형태에 따라 하나 이상의 필드로 구성된다. 즉, 데이터 부분은 여러 데이터가 들어갈 수 있다. - 링크 부분
☞ 다음 노드의 위치를 가리키는 포인터(주소) 값을 저장한다. 만약 다음 노드가 없는 마지막 노드인 경우에는 링크를 null으로 표현한다.
4. 다항식의 단순 연결 리스트 표현
다항식의 항을 단순 연결 리스트로 표현한다. 다항식을 표현하기 위한 노드의 구조는 각 항에 대해서 계수, 지수, 링크로 구성된다.
| 계수 필드 | 지수 필드 | 링크 필드 |
5. 다항식의 환형 연결 리스트 표현
다항식을 환형 연결 리스트로 표현하면 특정한 항을 검색하기가 쉬워진다. 일반적인 단순 연결 리스트의 단점인 항상 head부터 검색해야 한다는 단점을 보완할 수 있다. 언제든지 현재 노드에서 링크를 따라 검색하면 다시 자신으로 돌아오기 때문에 리스트의 시작인 head부터 검색하지 않아도 된다.
노드를 반환하는 경우 반환되는 노드들을 리스트 형태로 표현하여 가용공간에 저장하면 나중에 새로운 노드를 생성할 때 새로운 기억공간을 할당받지 않아도 된다. 만약 지정된 가용공간이 없는 경우메나 새로운 기억공간을 할당받아 사용한다.
6. 단순 연결 리스트의 역순
단순 연결 리스트는 리스트를 구성하는 노드들이 한쪽 방향으로 연결된 구조를 의미하며 삽입과 삭제가 쉽고, 기억장소를 낭비하지 않는 장점이 있다.
참고
독학사 교재