연결리스트

리스트

• 순서를 가진 데이터의 집합
• 동일한 데이터를 가지고 있을 수 있다.

연결 리스트란?

• 메모리의 동적 할당을 기반으로 구현된 리스트

순차 리스트와의 차이

순차리스트
 - 순차리스트는 배열을 기반으로 컴파일 타임에 메모리가 할당되어 크기가 변할 수 없음
 - 데이터들이 메모리에 순차적으로 저장되어 있기 때문에 인덱스에 대해 바로 접근이 가능
 - 마지막 원소가 아닌 임의의 인덱스의 삽입, 삭제 시 데이터를 옮기는 작업이 필요

 연결리스트
  - 각 원소들이 링크를 통해 연결되어 있음
  - 필요에 따라 메모리를 동적할당하여 추가하기 때문에, 가변적인 메모리 사용에 효율적임
  - 자료의 논리적인 순서와 메모리 상의 물리적인 순서가 순차적이지 않기 때문에, 임의의 인덱스의 접근이 불가능

구성요소

• 노드 : 연결 리스트에서 하나의 원소를 표현하는 building block. 데이터 필드와 링크 필드를 가지고 있음
• 데이터 필드 : 원소의 실질적인 값을 저장
• 링크 필드 : 다음 노드의 참조값(포인터)를 저장
• 헤드 : 연결 리스트에서 첫 노드에 대한 참조 값을 가지고 있음

종류

• 단순 연결 리스트 : 노드가 단 방향으로 연결된 리스트
• 이중 연결 리스트 : 각 노드별로 이전 노드와 다음 노드가 연결된 리스트
• 원형 연결 리스트 : 연결 리스트에서 tail 노드가 head노드가 연결되어 있는 리스트