Java-자료구조 2주차 연결리스트 - 2-1~3

강의명: Java로 구현하고 배우는 자료구조
2주차-연결리스트

2-1.연결리스트란?

-주 사용처: 순차적인 데이터나 많은 양의 데이터 처리
목적) 많은 양의 데이터를 적은 양의 메모리를 사용하여 저장

-종류

-특히, Double Linked List는 아래와 같이 연결된다

*Node

• 구성요소: 'next'란 이름의 포인터 + 'data'를 담는 객체
• 여기서 'next'란 포인터는 다음 노드를 가리킨다(즉, 다음 노드의 주소를 담는다)
• 연결 리스트의 1번째 Node: 'head'
• 연결리스트에 접근할 수 있는 유일한 방법은 head가 가리키는 포인터를 가지는 것!

*Array VS Linked List
공통점)

• 순서대로 데이터를 저장

차이점)

• 배열

public class ArrayEx01 {
	public static void main(String[] args) {
		String[] beer = {"Kloud", "Cass", "Asahi", "Guinness", "Heineken"};
		    // 인덱스 번호 :   0  ,    1   ,   2   ,     3      ,     4
		System.out.println(beer[0]); // Kloud
		System.out.println(beer[1]); // Cass
		System.out.println(beer[2]); // Asahi
		System.out.println(beer[3]); // Guinness
		System.out.println(beer[4]); // Heineken
	}
}

-필요한 요소에 비해 부족하거나 많은 경우가 있어 데이터를 넣고서 배열의 크기를 조정해야 하기에 대대적으로 재배치가 필요,
-인덱스가 존재하여 특정 요소로 접근 용이
(연결리스트의 경우, 순차 탐색이 필요하여 탐색 속도 하락)
참고)https://m.blog.naver.com/heartflow89/220950491600

• 연결 리스트: 항상 맞는 크키로 만들어지게 설계,
  데이터 추가/삭제가 용이
  참고)https://freestrokes.tistory.com/84

<정리>
-배열: 탐색, 정렬에 주로 사용
연결리스트: 순차적인 데이터/많은 양의 데이터 처리에 주로 사용

2-2.노드와 크기
*Node 생성 코드

// 노드 정의
	class Node<E>{
		E data; 
		Node<E> next;
		public Node(E obj){ // 생성자
			data=obj;
			next=null;
		}

• 이 노드가 연결리스트를 사용하지 않는 외부에서 건들 수 있게 만들면 노드의 위치를 바꾸거나, 정보를 잃는 상황이 일어날 수 있어 내부 클래스로 정의해 제한한다
  참고)내부클래스-https://jammdev.tistory.com/130

*연결 리스트의 생성 코드(with Node)

public class LinkedList <E> implements ListI<E>{
	// 노드 정의
	class Node<E>{
		E data;
		Node<E> next; // 다른 노드를 가리키는 포인터
		public Node(E obj){ // 노드 생성자
			data=obj;
			next=null;
		}
	}
    
	private Node<E> head; // 현재 1번째 노드 속 포인터
	private int currentSize; // 노드 개수를 세는 변수
	
    // 기본 연결리스트
	public LinkedList(){ // 연결리스트 생성자
		head=null;
		currentsize=null;
	}
}

-노드 자체는 내부클래스로 외부에서 건들 수 없게 만들기 위해 'private 변수 head'로 선언해 연결 리스트를 만든다

*왜 Node는 내부 클래스로 만들어야 할까?
=> 외부에서 Node 내 data의 접근을 막아 보안 유지

*Node의 크기[=='Node의 갯수']

• 모든 노드의 갯수를 구한다면 모든 Node를 세야 하기에 빅 오 표기법으로 O(n)이 된다.
  => 시간복잡도를 줄이기 위해(빠르게 계산하기 위해) 노드 갯수를 세는 변수[currentSize]를 만들어 관리하면 'currentSize'만 출력하여 빅 오 표기법으로 O(1)이 된다.

2-3.Boundary Conditions
=> 자료 구조를 만들 때 Error 발생 가능 조건

1. Empty data structure(자료구조가 비어있는 경우)
   -> 비어있는 경우와 그렇지 않는 경우가 다르게 작용되는가?

2. Single element in the data structure
   -> 요소가 하나만 존재하는 경우, 고려해야할 경우는?

3. Adding/Removing beginning of data structure
   -> 자료구조의 어느 요소를 추가/제거하는 경우 어떻게 되는가?
   (예시: head를 삭제)

4. Adding/Removing end of the data structure
   -> 자료구조의 어느 요소를 추가/제거하는 경우 어떻게 되는가?

5. Working in the middle(자료구조의 중간 영역을 건들어야 하는 경우)
   -> 항상 고려해야 하며, 가장 흔한 경우로 자료구조를 만들 때마다 고려해야 하는 상황

1) 자료 구조의 첫 번째 요소를 제거하거나 추가할 때 어떤 포인터를 고려해야 되나요?
=> head