---

⚡ Linked List

---

📌 연결리스트

🔷 특성

• 자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로 위치하고 있는 원소의 주소를 연결하여 하나의 전체적인 자료구조를 이룬다.
• 링크를 통해 원소에 접근하므로, 순차 리스트에서처럼 물리적인 순서를 맞추기 위한 작업이 필요하지 않다.
• 자료구조의 크기를 동적으로 조정할 수 있어, 메모리의 효율적인 사용이 가능하다.

🔷 노드

• 연결 리스트에서 하나의 원소에 필요한 데이터를 갖고 있는 자료단위
• 구성 요소
  1) 데이터 필드
  • 원소의 값을 저장하는 자료구조
  • 저장할 원소의 종류나 크기에 따라 구조를 정의하여 사용함
    2) 링크 필드
  • 다음 노드의 주소(Node link)를 저장하는 자료구조

🔷 헤드

• 리스트의 처음 노드를 가리키는 레퍼런스(노드)

---

📌 단순 연결 리스트 (Singly Linked List)

🔷 연결 구조

• 노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조를 가진다.
• 헤드가 가장 앞의 노드를 가리키고, 링크 필드가 연속적으로 다음 노드를 가리킨다.
• 최종적으로 NULL을 가리키는 노드가 리스트의 가장 마지막 노드이다.

1. 삽입
   1) 메모리를 할당하여 새로운 노드 new 생성
   2) 새로운 노드 new의 데이터 필드에 'B' 저장
   3) 삽입될 위치의 바로 앞에 위치한 노드의 링크 필드를 new에 복사
   4) new의 주소를 앞 노드의 링크 필드에 저장
2. 삭제
   1) 삭제할 노드의 앞 노드(선행노드) 탐색
   2) 삭제할 노드의 링크 필드를 선행노드의 링크 필드에 복사

🖥 Node.java

 // 데이터 필드, 다음 노드를 가리키는 링크 필드 하나로 구성
public class Node {
	public String data; // 제네릭 이용시 더 포괄적인 데이터 사용 가능
	public Node link; // 주소를 저장하기 위해 Node 자료형 사용
	
	public Node() {} // 기본 생성자
	
	public Node(String data) {
		this.data = data;
		this.link = null; // null은 알아서 초기화되기 때문에 필요 없는 코드
	}
    
    @Override
	public String toString() {
		return "Node [data=" + data + "]";
	}
}

🖥 SinglyLinkedList.java

public class SinglyLinkedList {
	// 필드
	private Node head; // 노드의 시작점
	private int size; // 연결리스트의 노드의 개수 (필수는 아니지만 있을 때 편하다)
	
	// 조회
	public Node get(int idx) {
		// 인덱스가 범위를 초과해버릴 때 예외 처리
		if(idx < 0 || idx >= size) {
			// null return 혹은 첫번째 노드나 마지막 노드 반환 등
			return null;
		}
		// idx 위치만큼 이동
		Node curr = head;
		for(int i = 0; i < idx; i++) {
			curr = curr.link;
		}
		return curr;
	}
	
	// 첫번째 위치에 원소 삽입
	public void addFirst(String data) {
		// 노드 생성
		Node node = new Node(data); // 생성자를 이용한 인스턴스 생성
		// 순서 중요! (head를 먼저 끊으면 이후의 것들이 가비지컬렉터에게 잡아먹힘)
		node.link = head;
		head = node; // head가 첫번째 원소를 가리킨다
		size++;
	}
	
	// 마지막 위치에 원소 삽입
	public void addLast(String data) {
		// 공백 리스트일 때는 처음에 넣는다.
		if(size == 0) {
			addFirst(data);
			return;
		}
		
		Node node = new Node(data);
		
		// 마지막 노드 탐색
		Node curr = head;
		while(curr.link != null) {
			curr = curr.link;
		}
		
		curr.link = node;
		size++;
	}
	
	// 중간 원소 삽입
	public void add(int idx, String data) {
		// 리스트 범위 초과 시
		if(idx < 0 || idx >= size) {
			System.out.println("잘못된 인덱스입니다.");
			return;
		}
		// 들어온 인덱스가 0(처음)일 시
		if(idx == 0) {
			addFirst(data);
			return;
		}
		// 들어온 인덱스가 마지막 위치일 시
		if(idx == size) {
			addLast(data);
			return;
		}
		
		Node pre = get(idx-1); // 조회 함수 이용
		
		Node node = new Node(data);
		node.link = pre.link;
		pre.link = node;
		size++;
	}
	
	// 첫 번째 원소 삭제
	public String remove() {
		if(head == null) 
			return null;
		
		String data = head.data;
		head = head.link;
		size--;
		
		return data;
	}
	
	// 중간 원소 삭제
	public String remove(int idx) {
		if(idx == 0)
			return remove(); // 주의! 함수를 리턴한 것이 아니라 함수의 결과값(문자열)을 리턴한 것!
		
		if(idx < 0 || idx >= size)
			return null;
		
		Node pre = get(idx-1); 
		Node rmNode = pre.link; // 삭제할 노드
		
		String data = rmNode.data;
		pre.link = rmNode.link;
		
		size--;
		
		return data;
	}
	
	// 연결리스트 내용물 출력
	public void printList() {
		Node curr = head;
		
		if(head == null) {
			System.out.println("공백 상태입니다.");
			return;
		}
		
		// 1. size를 쓰는 for문
		// 2. size를 쓰지 않는 while문 (현재)
		while(curr != null) {
			System.out.print(curr.data + " -> ");
			curr = curr.link;
		}
		System.out.println();
	}
}

🖥 Test.java

public class Test {

	public static void main(String[] args) {
		SinglyLinkedList list = new SinglyLinkedList();
		
		list.printList();
		
		list.addFirst("박영규");
		list.printList();
		
		list.addFirst("박영순");
		list.printList();
		
		list.addFirst("박영훈");
		list.printList();
		
		list.addLast("박민정");
		list.printList();
		
		System.out.println(list.get(0));
		System.out.println(list.get(-1));
		
		list.add(2, "박지원");
		list.add(4, "박씨");
		list.printList();
		
		list.remove();
		list.printList();
		
		list.remove(2);
		list.printList();
	}
}

---

📌 이중 연결 리스트

🔷 특성

• 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트
• 두 개의 링크 필드와 한 개의 데이터 필드로 구성

🔷 연결 구조

• 기존 단순 연결 리스트에서 prev가 이전 노드를, next가 다음 노드를 가리킨다.
• tail이 마지막 노드를 가리키게 만들 수도 있다.

1. 삽입
   1) 메모리를 할당하여 새로운 노드 new를 생성하고 데이터 필드에 'D'를 저장
   2) curr의 next를 new의 next에 저장하여 cur의 오른쪽 노드를 삽입할 노드 new의 오른쪽 노드로 연결한다.
   3) new의 주소를 curr의 next에 저장하여 노드 new를 cur의 오른쪽 노드로 연결한다.
   4) curr에 있는 링크 값을 new의 prev에 저장하여 curr를 new의 왼쪽 노드로 연결한다.
   5) new의 주소를 new의 오른쪽 노드의 prev에 저장하여 노드 new의 오른쪽 노드의 왼쪽 노드로 new를 연결
2. 삭제
   1) 삭제할 노드 curr의 오른쪽 노드의 주소를 curr의 왼쪽노드의 next에 저장하여 cur의 오른쪽 노드를 curr의 왼쪽 노드의 오른쪽 노드로 연결한다.
   2) 삭제할 노드 curr의 왼쪽 노드의 주소를 curr의 오른쪽 노드의 prev에 저장하여 curr의 왼쪽 노드를 curr의 오른쪽 노드의 왼쪽 노드로 연결한다.
   3) curr가 가리키는 노드에 할당된 메모리를 반환

🌟 배열 VS 연결리스트
삽입과 삭제 면에서는 연결리스트가 좋지만
조회 면에서는 배열이 더 좋다.