연결리스트(Linked List)

연결리스트(Linked List)

Abstract

• 불연속적인 메모리 위에 저장되는 선형 데이터 구조(배열은 메모리 공간이 연속적)
• 포인터를 사용해서 연결.
• 각 node는 데이터 필드 와 다음 노드에 대한 참조 를 포함하는 노드 로 구성

---

Linked List를 사용하는 이유

• 배열도 비슷한 유형의 선형 데이터를 저장하는데 사용할 수 있찌만 제한사항이 존재
  • 크기만큼 정적으로 메모리 공간을 연속적으로 할당
  • 연속적으로 할당하기때문에, 사용하지 않는 공간이 있더라고 그 공간을 다른 용도로 쓰지 못함 =>메모리 낭비가 클 수 있음
  • 배열의 크기는 고정되어 있기 때문에 미리 그 수를 할당받아야함(정적)
  • 크기를 초과할시 새로운 요소를 삽입하는 비용이 많이듦 -> 공간을 만들고, 기존 요소를 전부 이동

---

장점

1. 동적 크기
2. 삽입/삭제가 용이

---

단점

1. 임의로 노드에 접근할 수 없음(첫번째 노드부터 순차적으로 요소에 액세스 해야함, 이진탐색 불가능)
2. 각 노드마다 포인터를 저장하기 위한 추가 공간이 필요함