---

연결 리스트(Linked List)

---

1. Linked List

• 연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조

• 포인터를 사용해서 연결된다.

• 각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함하는 노드로 구성된다.

2. 사용 이유

• 배열의 제한 사항
  -> 배열의 크기는 고정되어 있다.
  -> 새로운 요소를 삽입하는 것은 비용이 많이 든다.(공간을 만들고, 기존 요소를 전부 이동시켜야 함)

• Linked List 장점
  -> 동적 크기
  -> 삽입/삭제 용이

• Linked List 단점
  -> 임의의 엑세스를 허용할 수 없다. 첫 번째 노드부터 순차적으로 요소에 엑세스를 해야 한다.
  -> 포인터의 여분 메모리 공간이 목록의 각 요소에 필요하다.