linked-list

데이터를 저장한 단위 메모리가 서로 연결되어 있는 자료구조이다.

단일 연결 리스트 ( singlt linked list ) : 리스트가 각 노드에 다른 노드를 가리키는 포인터가 하나씩만 있는 연결 리스트

 

출처: 유튜브 생활코딩

 

linked list VS array

• 구현방식
  • Array : 고정 크기 메모리를 사용한다.
  • Linked list : Node(구조체) 연결 방식을 사용한다.
• 메모리 효용성
  • Array : 낮음
  • Linked list : 높음
• 삽입 및 삭제 속도
  • Array : 느림 ( 원소 이동 필요 )
  • Linked list : 빠름 ( 원소 이동 필요 없음 )
• 원소 접근 속도
  • Array : 빠름
  • Linked list : 느림
• 구현 복잡도
  • Array : 간단
  • Linked list : 복잡

Singly linked list 관리

• 첫 번째 node에 접근하기 위한 pointer 변수 ( head pointer ) 가 반드시 필요하다.
• 마지막 node ( tail node ) 를 가리키는 pointer 변수 ( tail pointer ) 와 linked list 내의 실제 데이터를 저장하고 있는 node의 개수 ( linked list 크기) 를 저장해 놓으면 연결 리스트 관리가 매우 수월해진다.

기본 용어 정리

• node : linked list의 요소로 [데이터 영역 + 포인터 영역]으로 구성된다.
• head node & tail node : linked list 내의 node중 가장 첫 번째 데이터아 마지막에 위치한 node로 실제 데이터는 저장하지 않는다.
• head pointer : linked list 내의 첫 번째 node를 가리키는 포인터
• tail pointer : linked list 내의 마지막 node를 가리키는 포인터
• node count : linked list 내의 실제 데이터를 저장하고 있는 데이터 node의 개수

linked list의 기능

1. linked list 생성하기
2. node 추가하기
3. 전체 node 출력하기
4. node 검색하기
5. node 삭제하기
6. node 정렬하기
7. linked list 소멸하기