IT용어위키



연결 리스트

Linked List
자료를 임의의 기억공간에 저장시키고, 포인터를 이용하여 상호 연결시킨 선형 자료 구조
  • 실무적으로 아주 많이 쓰이는 자료구조
  • 블록 체인도 이 연결 리스트로 이루어져 있다.
  • 실무적으론 '연결 리스트'라는 말보단 '링크드 리스트'라는 말을 더 많이 쓴다.

1. 장단점

장점
  • 자료의 삽입 및 삭제가 용이
  • 기억장소의 이용 효율이 높음
단점
  • Access Time이 느림
  • 포인터를 위한 추가 공간 필요

2. 구조

각각의 노드는 2가지 값을 가진다.

  • 데이터
  • 링크
1 struct Node {
2 	int data;
3 	Node * next;
4 };

3. 동작

3.1. 읽기

연결 리스트.png

  • 헤드부터 순차적으로 읽는다.
  • Access Time이 느린 이유

3.2. 삽입

연결 리스트 삽입.png

  • 임시 노드를 생성한다.
  • 삽입할 위치 앞 노드와 뒷 노드를 취한다.
    • 앞 노드의 링크를 먼저 바꿔버리면 뒷 노드를 잃어버리므로 주의
  • 앞 노드의 링크를 임시 노드로 하고, 임시 노드의 링크를 뒷 노드로 한다.

3.3. 삭제

연결 리스트 삭제.png

  • 삭제 순서가 잘못되면 자료를 잃어버리는 상황이 발생되므로 주의
  • 삭제될 노드가 첫 노드일 경우
    • 첫 노드를 가리키는 포인터를 변경 해 준 후 삭제해야 한다.
  • 그 외의 경우
    • 대상 노드의 포인터를 취한다.
    • 대상 노드 앞 노드의 링크를 뒷 노드로 연결시킨다.
    • 대상 노드의 메모리를 해제한다.

4. 이중 연결 리스트

Double Linked List; Multi Linked List

항상 다음 노드만을 바라보고 있는 연결 리스트와 달리, 이전 노드와 다음 노드의 링크를 모두 가지고 있는 연결 리스트

  • 실무적으론 '이중 연결 리스트'라는 말보단 '링크드 리스트'라는 말을 더 많이 쓴다.
  • 이중 연결 리스트와 구분하기 위해 그냥 연결 리스트는 '단일 연결 리스트(Single Linked List)'라고도 부른다.

4.1. 장단점

단일 연결 리스트 대비
  • 장점: 연속적인 탐색&액세스가 이루어져야 하는 경우 탐색 시간 절감
  • 단점: 포인터를 위한 공간이 2배로 사용됨

이중 연결 리스트.jpeg


  출처: 공대위키(공대위키에서 최신 문서 보기)
  * 본 페이지는 공대위키에서 미러링된 페이지입니다. 일부 오류나 표현의 누락이 있을 수 있습니다. 원본 문서는 공대위키에서 확인하세요!