연결 리스트

**배열을 이용하면 시간복잡도가 상당히 커지게 된다.

배열은 탐색이 많을 경우 유리하다.

추가와 삭제가 반복되는 로직이라면 "연결 리스트" 를 사용하는게 유리**

연결리스트

각 요소를 포인터로 연결하여 관리하는 선형 자료구조
각요소는 노드라고 부르면 데이터 영역과 포인터 영역으로 구성된다.

연결리스트의 특징

• 메모리가 허용하는한 요소추가에 제한이 없다.
• 탐색은 O(n) 선형시간이 소요 (배열은 상수시간 소요)
  • 요소를 추가하거나 제거할 때는 O(1) 소요 텍스트

연결리스트의 구현은 세가지

1. Singly Linked List 단일 연결 리스트
2. Double Linked List 이중 연결 리스트
3. Circular Linked List 환형 연결 리스트

배열과 차이점

1. 메모리 차이 : 배열은 순차적인 데이터가 들어가기 때문에 메모리 영역을 연속적으로 사용,
   반면 연결리스트는 순차적이지 않기에 각 데이터가 퍼져있다.
2. 배열의 요소 추가,삭제는 선형시간, 연결리스트의 요소 추가,삭제는 상수시간이 소요된다.

1. Singly Linked List 단일 연결 리스트

: 가장 기본적이고 단순, head -> tail 까지 단방향 연결

• 헤드 포인터는 헤드를 가리키는 첫번째 요소.
• tail의 포인터 영역이 NULL값이면 더이상 갈곳이 없다는 뜻으로 가장 마지막 요소라고 볼 수있다.

연결리스트 핵심로직

요소 찾기 : 선형시간
요소 추가 : 상수시간 단, 추가하는부분 즉 탐색을 해야할시 선형시간이 소요된다.
요소 삭제 : 상수시간

Double Linked List

: 양방향으로 이어지는 연결리스트, 포인터가 두개이다.때문에 단일연결리스트보다 자료구조의 크기가 조금 더 크다.

요소 추가 : 상수시간
요소 삭제 : 상수시간

Circular Linked List

: 리스트의 tail이 head로 연결되게 한다.메모리를 아껴쓸 수 있다. 중간에서 탐색을 시작해도 한바퀴를 다 돌 수가 있다.

단일연결리스트 구현 코드

요소인 Node class와 SinglyLinkedList로 구성된다.

인강 출처 : [프로그래머스](https://programmers.co.kr/learn/courses/13213)