Linked List

자료를 임의의 기억공간에 저장시키고, 포인터를 이용하여 상호 연결시킨 선형 자료 구조

• 실무적으로 아주 많이 쓰이는 자료구조
• 블록 체인도 이 연결 리스트로 이루어져 있다.
• 실무적으론 '연결 리스트'라는 말보단 '링크드 리스트'라는 말을 더 많이 쓴다.

장단점

구조

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

• 데이터
• 링크

struct Node {
	int data;
	Node * next;
};

동작

읽기

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

삽입

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

삭제

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

이중 연결 리스트

Double Linked List; Multi Linked List

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

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

장단점

단일 연결 리스트 대비

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