배열 리스트와 연결 리스트

리스트 (List)

List 란 ⁉️

• 순서가 있는 자료를 다루는 추상 자료형(ADT)
• 추상 자료형이기 때문에, 구현 방법이 명시되어 있지 않다.
• 리스트를 구현한 대표적인 자료구조에는 배열리스트와 연결리스트가 있다.
  

배열 리스트 (Array List)

Array List 란 ⁉️

• 내부적으로 배열을 이용하여 구현한 리스트
• 인덱스를 기반으로 저장하고 있는 객체에 임의 접근(Random Access)한다.
• 배열의 크기가 가변적이기 때문에 유연한 자료구조
• 데이터가 연속적으로 존재하며, 그 순서가 유지된다.

연결 리스트 (Linked List)

Linked List 란 ⁉️

• 리스트를 구현한 자료구조로 자료를 연결하여 관리하는 자료구조
• 자료의 순서는 정해져 있지만, 메모리 상에서의 연속성은 보장하지 않는 것이 특징이다.
• 때문에, 메모리를 미리 할당하지 않고, 동적으로 할당받는다. 즉, 자료의 추가/제거가 용이하다.
• 첫번째 데이터를 시작으로 하여 원하는 객체를 찾기 위해 순차 접근(Sequential Access)한다.

연결 리스트의 종류 🔍

1. 단방향 연결 리스트 - 자료의 값과 연결 정보를 가진 노드(node)로 구성
   

2. 양방향 연결 리스트 - 양방향으로 노드를 연결하는 이중 연결 구조
   

3. 원형 연결 리스트