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

※ 단순연결 리스트란?

• 하나의 링크 필드를 가진 노드들이 모두 자기 후속노드와 연결되어 있는 노드 열
• 마지막 노드의 링크 필드는 리스트의 끝을 표시하는 null값을 가짐
• 별칭 : 선형 연결 리스트(linear linked list), 단순 연결 선형 리스트(singly linked linear list), 연결 리스트(linked list), 체인(chain)
• 단순 연결 리스트의 예
  

---

노드 구조 정의

● 원소 삽입 알고리즘

• 예) 리스트 L에 원소 “Han”을 “Cho”와 “Kim” 사이에 삽입
  1. 공백노드를 획득함. newNode라는 변수로 가리키게 함
  2. newNode의 data 필드에 “Han”을 저장
  3. “Cho”를 저장하고 있는 노드의 link 값을 newNode의 link 필드에 저장
  (즉 “Kim”을 저장하고 있는 노드의 주소를 newNode의 link에 저장)
  4. “Cho”를 저장한 노드의 link에 newNode의 포인터 값 을 저장
• 리스트의 기존 원소들을 이동시킬 필요 없음
• 부수적인 link 필드를 위해 저장 공간을 추가로 사용
  

● 원소 삭제 알고리즘

• 예) 리스트 L에서 원소 “Han”을 삭제
  1. 원소 “Han”이 들어 있는 노드의 선행자 찾음 (“Cho”가 들어있는 노드)
  2. 이 선행자의 link에 “Han”이 들어있는 노드의 link 값을 저장
  

● 메모리의 획득과 반납

• 연결 리스트가 필요로 하는 두 가지 연산

  • 데이타 필드와 하나의 링크 필드를 가진 하나의 공백 노드 를 획득하는 방법
  • 사용하지 않는 노드는 다시 반납하여 재사용하는 방법

• 자유 공간 리스트 (free space list) 가 있는 경우

  • getNode()
    - 데이타와 링크 필드로 되어 있는 새로운 공백 노드를 가용 공간 리스트로부터 할당받아 그 주소를 반환하는 함수
  • returnNode()
    - 포인터 변수 P가 지시하는 노드를 가용 공간 리스트에 반 환하는 함수
    - 프로그래밍 언어에 따라 필요한 경우도 있고 필요하지 않은 경우도 있음
    - Java와 같이 사용하지 못하는 노드를 자동으로 관리해 주 는 언어에서도 사용자가 직접 관리할 필요가 있는 경우도 있음

---

기본 연산

● 리스트 생성 알고리즘

• 앞의 두 함수를 사용한 리스트 생성 알고리즘
  

• 리스트 생성 알고리즘을 점 표기식으로 작성한 경우
  
  

● 노드 삽입 알고리즘

• 리스트 L의 첫번째 노드로 data 값이 x인 노드를 삽입
  

• 원소값이 x인 노드를 p가 가리키는 노드 다음에 삽입
  

  • (a) L이 공백 리스트인 경우
    
  • (b) P가 null인 경우
    
  • (c) L과 p가 null이 아닌 경우
    

• 리스트 L의 마지막 노드로 원소값 x를 첨가
  

● 노드 삭제 알고리즘

• 리스트 L에서 p가 가리키는 노드의 다음 노드를 삭제
  

• 리스트에서 마지막 노드를 삭제하는 프로그램
  
  

  • currentNode와 previousNode의 동작 과정
    － currentNode 포인터가 어떤 노드를 가리키면 previousNode 포인 터는 currentNode가 가리키는 노드의 바로 직전 노드를 가리키도록 함
    － currentNode가 리스트의 마지막 노드를 가리키게 될 때 previousNode는 마지막 두 번째 노드를 가리키게 됨
    

● 리스트 역순 알고리즘

• 리스트를 역순으로 만드는 알고리즘
  

● 리스트 연결 알고리즘

• 두개의 리스트 L1과 L2를 하나로 만드는 알고리즘
  

● 원소 탐색 알고리즘

• 데이타 값이 x인 노드를 찾는 알고리즘
  

• 데이타 값이 x인 노드를 찾는 알고리즘의 Java 구현
  

● 리스트 출력 알고리즘

• 연결 리스트의 프린트
  

---

💻 예제 프로그램

● ListNode 클래스

• data 필드와 link 필드를 가진 객체 구조를 정의
• 이 필드들을 초기화시키기 위해 생성자 정의

● LinkedList 클래스

• 실제 연결 리스트를 정의
• head 필드 : private, ListNode 타입으로 선언, 연결 리스트의 첫 번째 노드를 가리킴

● LinkedList 생성의 예

• LinkedList L = new LinkedList();
  

• L에 노드가 연결되어 있는 경우
  

◆ 단순 연결 리스트의 처리