연결리스트의 개념

📌 연결리스트의 개념

💡 자기참조 구조체

1. 동일한 타입의 구조체에 대한 포인터를 속성으로 포함하는 구조체
2. Link
   1. Node 구조체에 대한 포인터 -> 메모리의 주소를 가리키는 자료형
   2. 여러 개의 Node 구조체를 연결하는 역할

💡 연결리스트

1. 단순 연결리스트(Singly Linked List)
   1. 자기 참조 구조체(Node)들의 연결
   2. 천번째 노드에 대한 포인터만 유지
      1. 리스트의 이름 = 첫번째 노드의 수조
   3. 이후 노드들은 구조체의 Link 포인터를 통해 참조
   4. 마지막 노드의 Link 포인터는 NULL로 설정한다.

2. 다른 연결리스트
   1. 이중 연결 리스트(Doubly Linked List)
      1. 앞 뒤의 노드들의 정보를 가지고 있다.
   2. 원형 연결 리스트(Circular Linked List)
      1. 마지막 노트와 첫노드를 연결

3. 연결리스트 연산 - 순회
   1. 연결리스트의 길이 계산
      1. 각각의 노드를 정확히 한번만, 체계적인 방법으로 방문하는 과정
   2. 삽입 및 삭제를 하더라도 노드의 위치는 달라지지 않는다.

💡 배열과 연결 리스트의 비교

1. 저장 방식의 차이 -> 메모리의 인접한 곳에 저장한다.
   1. 배열 : int Array[4];
      1. 다음 데이터에 대한 주소를 알 필요가 없다.

2. 연결리스트 : struct node에 대한 네 번의 malloc
   1. 각 노드들은 메모리의 여러 곳에 나누어 저장한다.
   2. Link를 이용하여 다음 노드의 주소를 유지한다

2. 메모리 사용 측면
   1. 저장될 데이터의 수를 안다면 배열이 효과적이다.
   2. 데이터의 수를 모를 경우, 연결리스트가 유리하다.
      1. 새로 데이터가 입력될 때마다, malloc 실행 후 연결

3. 정렬된 데이터의 순서 유지
   1. 배열
      1. 데이터가 추가될 때 기존 데이터의 위치 변경이 가능하다.
      2. 이진 검색이 가능하다.

2. 연결리스트
   1. 기존 데이터의 위치 변경은 발생하지 않는다.
   2. 이진 검색이 불가능하다.