연결 리스트(Linked List)

연결 리스트란?

자료(Data)가 순차적으로 연결되어있는 구조이다. 노드(Node)라는 객체로 이루어진다.
노드는 Data, Next Node로 구성된다.

연결 리스트의 특징

• 논리적으로 순차적이나, 메모리가 물리적으로 순차적 구조를 띄지 않습니다.
• 삽입, 삭제 시 데이터 재구성이 용이합니다.
• 다음 주소를 저장할 데이터 공간이 필요합니다.
  ➡ 약속된 배열의 인덱스와는 달리, 다음 원소의 주소를 기억해야 합니다.

연결 리스트의 종류

• 단순 연결 리스트
  
• 원형 연결 리스트
  
• 이중 연결 리스트
  

연결 리스트의 장점

• 데이터 삽입, 삭제가 빠릅니다.
  ➡ 빈번한 삽입 삭제 시 배열보다 유리

• 메모리를 효율적으로 관리하기 용이합니다.
  ➡ 데이터 크기가 가변적

연결 리스트의 단점

• 하나의 데이터에 배열보다 큰 메모리 공간이 필요합니다.
• 다음 원소의 주소를 기억해야 하기 때문에 탐색이 느립니다.