링크드 리스트

링크드 리스트

링크드 리스트는 동적할당이 유용하고, 삽입/삭제가 유용합니다.(일반적인 리스트에서의 밀리는 시간을 고려하지 않음) 그러나 탐색시간이 오래 걸린다는 단점이 있습니다.

구조

• 노드: 데이터와 하나 이상의 링크로 이루어 진다. 링크를 위한 추가 공간이 필요.
• 헤드포인터: 헤드 노드만 알면, 링크로 연결된 모든 노드에 순차적으로 접근 가능.(헤드노드 전)
• 헤드 노드: 연결 리스트의 시작 노드
• 헤드 포인터: 머리 노드의 주소를 저장하는 가장 중요한 변수
• 꼬리 노드: 마지막 노드, 꼬리 노드의 링크를 처리하는 방식에 따라 단순 연결과 원형 연결로 구분

종류
단순 연결 리스트: 하나의 방향으로만 연결된 리스트. 노드는 하나의 링크만 가지며 꼬리 노드에는 마지막 노드라는 None을 가진다.

원형 연결 리스트: 꼬리 노드의 링크가 머리 노드를 가리킴. 어떤 노드에서 시작하더라도 다른 모든 노드를 찾아갈 수 있음. 종료 조건 처리에 유의!

이중 연결 리스트: 하나의 노드가 이전 노드와 다음 노드의 링크를 모두 가짐. 어떤 노드에서 이전 노드를 찾을 수 있어서 유용하다. 링크를 이중으로 정확하게 유지해야 하므로 코드가 복잡함.

밑의 그림을 참조하면 이해하기 수월할 것 이다.