[자료구조] 연결 리스트 Linked List

 

---

 

1. 리스트의 한계

• 중간에 값을 삽입하거나 삭제할 경우 뒤 데이터의 이동(shift)이 필요함
• 리스트에 얼마나 원소가 들어올 지 예상할 수 없기 때문에 비효율적으로 데이터가 관리될 수 있음

 

2. 연결 리스트

• 리스트의 한계를 해결하기 위해 등장
• 각 노드는 데이터와 링크로 구성되어 링크에 다음 노드 정보를 저장함
• 가장 앞의 노드는 헤드 노드, 가장 뒤의 노드는 테일 노드라고 하고 테일 노드의 링크는 none으로 비워둠
• 헤드 포인터는 헤드 노드의 주소를 저장하는 가장 중요한 정보

 

3. 종류

단순 연결 리스트

• 각 노드는 하나의 링크만 가지며 다음 노드의 주소를 가리킴
• 테일 노드의 링크에는 none 저장

원형 연결 리스트

• 테일 노드의 링크에 헤드 노드의 주소를 넣어 헤드 노드를 가리키게 함
• 아무 노드에서 시작해도 링크를 타고 이동하면 다른 모든 노드에 접근할 수 있음
• 노드들을 순서대로 방문할 때 종료 조건이 되는 노드를 찾는 것이 어려울 수 있음

이중 연결 리스트

• 하나의 노드에 이전 노드와 다음 노드의 링크를 모두 갖도록 하는 형태
• 어떤 노드든 이전 노드나 다음 노드를 바로 찾아갈 수 있다는 장점이 있음
• 편리한 만큼 노드를 이중으로 관리해야 하므로 코드가 복잠해 질 수 있음