#2-1. 연결 리스트

연결리스트란 대부분의 알고리즘에서 사용하는 자료구조이다. 연결리스트의 장점은 다음과 같다.

1. 프로그램 실행 중에도 동적으로 새로운 노드를 삽입하거나 삭제하기 간편하다.
2. 링크라는 개념을 통해 물리 메모리를 연속적으로 사용하지 않아도 되므로 관리가 편하다.
3. 데이터를 구조체로 묶어서 포인터로 연결할 수 있다.

필자의 블로그에서 연결리스트를 다룬 포스팅이 있으니 참조하자.

https://udangtangtang-cording-oldcast1e.tistory.com/18

[연결리스트] #1. 연결리스트의미와 종류

연결리스트

헤드 노드	데이터를 저장하지 않는다. 단지 연결리스트의 시작 부분을 나타낸다.
테일 노드	테이터를 저장하지 않는다.

헤드 노드와 테일 노드는 연결리스트의 시작과 끝 부분을 파악하기 위해 사용하며 묵시적으로 데이터를 저장하지 않는다.

따라서 결국 데이터가 저장되는 노드는 연결리스트의 처음과 끝을 가리키는 노드 사이에 있다.

 

위의 사진을 보면 헤드 노드부터 화살표 방향으로 다음 노드를 가리키는데, 계속 진행되다 보면 테일 노드는 아무것도 가리키지 않는다. 이를 단일 연결리스트라 한다.