[연결 리스트]

포인터로 연결 리스트 만들기 

class Node<E>{
   E data; //데이터를 참조
   Node<E> next; //다음 노드를 참조
}

Node<E>는 데이터용 필드인 data와는 별도로 자기 자신과 같은 클래스형의 인스턴스를 참조하는 (가리키는) 참조용 필드 next를 가진다. (이런 클래스 구조를 자기 참조 (self-referential)형이라고 함)

 

Node<E>는 제네릭으로 구현되므로 데이터형 E는 임의의 클래스형이 허용된다. 

 

필드 data의 자료형인 E가 참조형이므로 클래스형 변수 data가 나타내는 것이 데이터 그 자체가 아니라 데이터를 넣어 두는 인스턴스에 대한 '참조'이기 때문이다. 

 

👉 다음 노드를 참조하는 next를 뒤쪽 포인터이다. 뒤쪽 포인터 next에 넣어 두는 것은 다음 노드에 대한 참조이다. 다음 노드가 없는 '꼬리 노드'의 뒤쪽 포인터 값을 널을 참조한다. 

 

public class LinkedList<E>{
  //노드
  class Node<E>{
    private E data; //데이터 
    private Node<E> next; //뒤쪽 포인터 (다음 노드 참조)

    //생성자
    Node(E data, Node<E> next){
      this.data = data;
      this.next = next;
    }
  }
  private Node<E> head; //머리 포인터 (머리 노드 참조)
  private Node<E> crnt; //선택 포인터 (선택 노드 참조)
}

👆 노드의 자료형이 클래스 Node<E>형인 연결 리스트를 클래스 Linked List<E>로 구현했다. 

 

연결 리스트는 중복을 허용한다.

head 포인터에 값을 넣고 next에 Node타입인 다음 노드를 넣어준다.  

 

---

노드 클래스 Node<E>

노드 클래스 Node<E>는 연결 리스트 클래스 Linked List<E> 안에 선언되어 있다. 

• data: 데이터 (데이터 참조: 형은 E)를 나타낸다. 
• next: 뒤쪽 포인터(다음 노드 참조: 형은 Node<E>)를 나타냅니다.
• 생성자: Node<E>의 생성자는 매개변수 data, next에 전달 받은 값을 해당 필드에 대입한다. 

연결 리스트 클래스 LinkedList<E>

• head: 머리 노드를 가리킨다. (머리 포인터)
• crnt: 현재 선택한 노드를 가리킨다. 리스트에서 노드를 '검색'하고 해당 노드를 선택한 뒤, 바로 그 노드를 '삭제'하는 등의 용도로 사용한다. 선택 포인터라고 부름

 

생성자 LinkedList

연결 리스트 클래스 LinkedList<E>의 생성자는 노드가 하나도 없는 비어 있는 연결 리스트를 생성한다.

//생성자
public LinkedList(){
   head = crnt = null;
}

이 생성자는 머리 포인터 head에 null을 대입한다. Head는 제일 처음 노드!!!

제일 처음 노드를 삭제하면 그 뒤에 있던 두번째 노드가 head가 된다. 

crnt에는 현재 검색 중인 노드가 들어감. 

검색을 하게 되면 crnt에 노드 안에 있는 data를 담고 찾길 원하는 값이 나올때까지 반복한다. 

---

1. 연결 리스트가 비어 있는지 판단하는 방법

노드가 하나도 없는 상태 (빈 연결 리스트). 

head == null

연결 리스트가 비어 있는지 확인

 

2. 노드가 1개인 연결 리스트를 판단하는 방법 

연결 리스트에 노드가 1개만 있는 상태. 머리 포인터 head 가 가리키는 곳은 머리 노드 A이다. 

head.next = null; //노드가 한 개인지 확인

머리 노드 A는 리스트의 꼬리 노드이기도 하므로 그 뒤쪽 포인터 값은 null

 

3. 노드가 2개인 연결 리스트를 판단하는 방법

머리 노드는 A, 꼬리 노드는 B. 이때 head가 가리키는 노드 A의 next는 노드 B를 가리킵니다.