자료구조

링크드 리스트

[자료구조] Linked List

[자료구조] Linked List

자료구조 중 가장 간단한 형태인 Linked List에 대해 정리했습니다.

노드

• 링크드리스트의 기본단위로서, 데이터를 저장하는 데이터 필드와 다음 노드를 가리키는 링크 필드(포인터)로 구성된다.

포인터

• 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

헤드

• 링크드 리스트에서 맨 처음 위치하는 노드를 의미한다.

• 리스트 전체를 참조하는데도 사용한다.

테일

• 링크드 리스트에서 마지막 위치하는 노드를 의미한다.

• 이 노드의 포인터는 Null을 가리킨다.

장점

• 단순한 구조로 이루어져 있어서 구현이 편하고 데이터의 추가, 삽입, 삭제가 쉽다.

• 현재 노드가 가지고 있는 포인터 정보를 사용하여 추가적인 연산 없이 다음 노드를 가져올 수 있음

단점

• 노드에는 다음 노드를 가르키는 포인터가 필요하기 때문에 메모리가 추가로 필요

• 헤드 노드의 정보만 가지고 있기 때문에 특정 위치에 있는 노드를 탐색하는데 많은 연산이 필요함