[자료구조] 단순 연결리스트

단순/단일 연결리스트

• 하나의 링크 필드를 이용하여 연결
• 마지막 노드의 링크값은 다음 노드가 없으므로 그 값을 NULL(‘\0’)로 설정
• 헤드 포인터는 첫 노드의 위치를 가리킴

 

단순 연결리스트의 구현

• 헤드포인터(head pointer)
  
  
  • 연결 리스트의 맨 처음 노드를 가리키는 포인터
  • 예) 위 그림에서 p1은 전체 리스트를 가리키는 헤드 포인터 역할
• 노드 : 데이터 필드와 링크 필드의 구조체로 정의
  

1. 노드의 생성: new를 이용하여 동적 메모리 할당
2. 데이터 필드와 링크 필드 설정
3. 두번째 노드 생성과 첫번째 노드와의 연결

구현시 유의할 점 

• 헤드 포인터 점검
  
  
  • 연결 리스트에서 노드 삭제/삽입 등의 변경 작업시, 헤드 포인터가 계속 잘 유지되도록 신경을 쓰자!
• NULL 포인터 검사 
  
  
  • 포인터가 NULL값을 가지는 경우에 항상 신경을 쓰자!
  • 특히, 헤드 포인터 등이 NULL 일 때와 아닐 때를 구분하여 코딩
  • NULL 값을 갖는 포인터에 대해 ‘->’ 연산자 사용 금지
  • (예) ptr이 NULL일 수도 있는 경우에 검사 없이 ptr->link 등을 사용하면 오류 발생 -> if(ptr != NULL) ptr = ptr->link;
• 실행 순서 판단
  
  
  • 연결리스트 관련 연산시 작업 순서가 매우 중요함을 기억하자!
• 메모리 활용
  
  
  • 동적 메모리 할당을 요청하는 malloc()/new 함수로 얻은 기억장소가 불필요하게 되었을 경우, 가능하면 즉시 free()/delete 함수를 이용하여 반납하자. (메모리 사용 효율을 위해)