[자료구조] 연결리스트 (Linked List)

연결리스트(Linked List)란?

연결리스트 또는 링크드리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다. 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당한다. 단일 연결리스트, 이중 연결리스트, 원형리스트 등이 있다.

1) 특징

- 크기가 고정되어 있지 않기 때문에 데이터의 추가/삭제가 용이하다.

- 빈 엘리먼트는 허용하지 않지만(값에 Null을 넣을 수는 있음), 중복 엘리먼트는 허용한다.

- 열거(Enumerate)하여 값을 찾기 때문에 특정 데이터 접근이 어려운 단점이 있다(그러나 배열에서는 자료마다 번호가 있어서 특정한 자료를 불러내기가 편리하다).

*탐색 또는 정렬을 자주 하면 배열을, 추가/삭제가 많으면 연결 리스트를 사용하는 것이 유리하다. 

- 이중 연결리스트는 단일 연결리스트에 비해 노드 삭제에 효율적이지만 그만큼 메모리를 더 차지한다.

- 원형 연결 리스트는 노드 추가시 효율적. 그러나 구현이 단일/이중 연결리스트에 비해 어렵다.

2) 종류

단일 연결 리스트

단일 연결 리스트의 구조

단일 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

이중 연결 리스트

이중 연결 리스트의 구조

이중 연결 리스트의 구조는 단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

원형 연결 리스트

단순 원형 연결 리스트의 구조

원형 연결 리스트는 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.