연결 리스트 - 단일 연결 리스트

단일 연결 리스트 (singly linked list)

• 데이터를 연결(linked) 형태로 표현
• 리스트 내의 각 항목들이 순차적으로 저장될 필요 없이 기억 장소 내 어디든 저장되어 있어도 됨
• 다음 항목을 찾기 위해 각 항목들은 다음 항목을 가리키는 포인터를 갖고 있음
• 이 포인터를 링크(link)라고 부름

• 단일 연결 리스트 기억 장소 내의 표현
  • 리스트 각 항목은 기억 장소의 순서대로 위치하지 않는다.
  • 링크라는 필드를 이용하여 리스트 원소들의 순서를 나타냄
  • 리스트 끝에는 더 이상 원소가 없다는 것을 나타내기 위하여 마지막 원소의 링크 필드에 NULL(역슬래시)로 표시

• 단일 연결 리스트의 기본 연산

  • 노드 생성
  • 노드 삽입
  • 노드 삭제

• 단일 연결 리스트의 노드 생성1

  • 가용 기억 공간 중에서 리스트에 연결할 수 있도록 하나의 노드를 획득
  • 그 노드의 주소를 새로운 포인터에게 부여
  • HEAD 포인터가 새로 생성된 노드를 가리키게 함
  • 노드에 데이터 저장

• 단일 연결 리스트의 노드 생성2
  • 리스트에 노드가 하나도 없을 때 새로운 노드 1개를 삽입하는 경우
  • 새로운 노드를 얻어와서
  • HEAD가 새로운 노드를 가리키게 하고
  • 새로운 노드의 링크를 NULL로 설정

• 단일 연결 리스트의 노드 생성3
  • 2개의 노드를 생성한 후
  • 첫 번째 노드에 데이터 A를 저장하고
  • 두 번째 노드에 데이터 B 저장

• 단일 연결 리스트의 노드 삽입
  • 노드1과 노드2 사이에 새로운 노드를 삽입할 경우
  • 노드1이 새로운 노드를 가리키고
  • 새로운 노드가 노드2를 가리키게 함

• 단일 연결 리스트의 노드 삽입의 경우
  • 리스트 맨 처음에 노드 삽입
    • 새로운 노드 얻어와서
    • 새로운 노드가 두 번째 노드를 가리키고
    • HEAD가 새 노드를 가리키게 함

• 리스트 맨 마지막에 노드 삽입
  • 새로운 노드를 얻어와서
  • 마지막 노드가 새로운 노드를 가리키고
  • 새로운 노드의 링크로 NULL값을 갖게 함

• 임의의 노드 X 다음에 삽입
  • 새로운 노드를 얻어와서
  • 새로운 노드가 임의의 노드 X 다음 노드를 가리키고
  • 임의의 노드 X가 새로운 노드를 가리키게 함

• 단일 연결 리스트의 노드 삭제
  • 맨 처음 노드 삭제
    • 먼저 노드의 유무 확인 : 삭제할 노드가 없으면 언더플로우 발생
    • 삭제할 노드의 데이터는 저장해 놓고, 주소는 유 용공간에 추가

• 마지막 노드 삭제
  • 마지막 노드를 찾아서 삭제
  • 마지막 이전 노드의 링크를 NULL로 설정

• 중간 노드 삭제
  • 삭제하려는 노드 X 노드 앞의 노드 링크에 X 노드가 갖고 있는 링크 값을 저장하면 자연히 X노드는 리스트에서 삭제