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

연결 리스트란?

연결 리스트는 값과 다음 노드에 대한 포인터(주소값)으로 이루어진 선형 리스트이다. 마지막 노드는 Null값을 갖는다. 연결리스트는 연속적인 주소 값을 갖는 배열과 자주 비교된다.

노드의 구성에 따라 단순 연결 리스트, 이중 연결리스트, 원형 연결 리스트가 있다

 

※ 연결 리스트와 배열의 비교

 

배열
특징	값이 연속된 메모리에 순차적으로 저장
장점	- 인덱스를 통한 빠른 접근이 가능 - 구현이 쉽고 직관적이다
단점	- 미리 값을 할당하므로 저장공간이 부족할 경우 오류가 발생 - 반대로 너무 많은 저장공간을 할당할 경우 메모리 낭비가 커짐 - 추가, 삭제 연산을 할 때 연산수가 많아짐 -> 원소의 이동수가 많아진다

 

배열: 연속적인 인덱스값을 갖는다

 

 

연결 리스트
특징	- 값이 연속된 메모리에 저장되지 않고 임의 주소에 저장됨 - 값을 저장하는 데이터 필드와 다음 노드를 가리키는 링크 필드로 구성
장점	- 필요할 때마다 노드를 할당하므로 필요한만큼만 메모리를 사용 - 추가, 삭제 연산 수행 시 배열에 비해 훨씬 빠르다
단점	- 연결 리스트 안의 특정 데이터에 접근할 때, 처음부터 순회해야 한다 - 다음 노드의 주소를 같이 저장해야하므로 추가 메모리가 필요

연결리스트: 데이터와 주소값을 저장한 노드들로 구성된다