Node : 너와 나의 연결! 고리!

📖 연결 리스트란?

• 연결 자료구조에서 자료를 노드(node)라 칭함
• 각 노드는 데이터 필드와 링크 필드로 구성
• 데이터의 접근은 항상 맨 처음 노드(head) 혹은 주소를 알고 있는 노드부터 시작
• 한 쪽 반향 또는 반대 방향으로 순회(travel) 가능, 그러나 임의 접근은 불가
• 명시적으로 끝이 있는 경우와 끝에서 다시 처음으로 연결된 경우로 나뉨
• 연결 리스트의 마지막 노드의 링크 필드는 null
  head → node1 → node2 → node3 → tail → null
  
  

---

1. 선형 자료구조의 고민

• 자료가 많아질수록 관리 비용이 점점 커짐
• 연속된 저장공간을 확보하는 것 자체가 어려움
  → 연결 자료구조를 통해 데이터를 여기 저기 흩어 저장하되, 링크 필드로 연결해놓자!
  
  

2. 연결 리스트의 종류

• 단일(singly) 연결 리스트 : 링크 필드 하나
• 이중(doubly) 연결 리스트 : 링크 필드 둘, 순방향과 역방향
• 원형(circular) 연결 리스트 : 링크 필드 하나, 끝에 null 없음, 뫼비우스의 띠처럼 쭉 연결!
• 원형 이중(circular doubly) 연결 리스트 : 링크 필드 둘, 끝이 null 없음
  
  

3. 자료의 추가

• 끼워 넣은 위치의 선행 노드, 후행 노드의 참조(주소) 확보
• 선행 노드의 링크는 신규 노드의 참조(주소)로 할당
• 신규 노드의 링크는 후행 노드의 참조(주소)로 할당
  
  

4. 자료의 삭제

• 삭제할 노드의 선행 노드 확보
• 선행 노드의 링크에 삭제한 노드의 링크 값 대입
  (= 선행 노드가 삭제한 노드를 넘어 그 다음 노드와 연결되도록)
  
  

5. 장점과 단점

🟩 장점

• 자료의 추가, 삭제 비용이 순차 자료구조에 비해 낮고, 자료 개수에 상관 없이 일정함
• 연속되 큰 메모리 공간이 없어도 구현 가능함

🟥 단점

• 알고리즘이 복잡함
• 링크를 위한 메모리를 추가로 사용해야함
• 자료의 임의 접근이 불가하여, 항상 시작 노드 또는 주소가 알려진 노드로부터 순회해야함

🟨 이럴 때 사용

• 자료의 추가, 삭제가 빈번하게 일어나는 경우
• 개별 자료의 임의 접근보다 전체 자료에 대한 full scan이 많은 경우

이미지 출처: 생활코딩 Linked list 개념 6 - Array list VS Linked list - Data Structure