[자료구조와 알고리즘] 연결 리스트

지수·2021년 9월 1일
0

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


📖 연결 리스트란?

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


1. 선형 자료구조의 고민

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

2. 연결 리스트의 종류

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

3. 자료의 추가

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

4. 자료의 삭제

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

5. 장점과 단점

🟩 장점

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

🟥 단점

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

🟨 이럴 때 사용

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


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

profile
사부작 사부작

0개의 댓글