[CS / 자료구조] List

링크드 리스트

 

 

• 링크드 리스트란 노드를 연결해서 만드는 리스트
• 헤드 : 리스트의 첫 번째 노드
• 테일 : 리스트의 마지막 노드

 

노드 : 리스트 내의 각 요소

• 데이터
• 다음 노드에 대한 포인터

링크드 리스트의 주요 연산

• 노드 생성 / 소멸
• 노드 추가
• 노드 탐색
• 노드 삭제
• 노드 삽입

장점과 단점

• 장점
  • 새로운 노드의 추가, 삽입, 삭제가 쉽고 빠름 O(1)
• 단점
  • 특정한 노드를 찾는데 걸리는 시간이 배열보다 느림. 최악의 경우 N번 탐색 O(N)
  • 포인터 때문에 각 노드마다 4byte의 메모리가 추가로 발생

더블 링크드 리스트(양방향 링크드 리스트)

 

 

• 양방향 탐색이 가능한 리스트
• 다음 노드를 가르키는 포인터 외에 이전 노드를 가르키는 포인터도 가지고 있음

 

환형 링크드 리스트(원형 링크드 리스트)

 

• 헤드와 테일이 연결되어 있는 링크드 리스트
• 헤드는 자신의 앞 노드로써 테일을 가리킴
• 테일은 자신의 뒷 노드로써 헤드를 가리킴
• 따라서 처음 링크드 리스트의 노드를 생성할 때 헤드는 헤드 자기자신을 가리켜야 함(헤드의 다음 노드는 헤드 자신이고, 헤드의 전 노드 역시 헤드 자신임)