LinkedList

연결리스트

• 자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로 위치하고 있는 원소의 주소를 연결하여 하나의 전체적인 자료구조를 이룬다.
  • 논리적 구조 : 사람이 이해하는 구조
  • 물리적 구조 : 실제 메모리 상에 저장되는 구조

• 링크를 통해 원소에 접근, 순차 리스트와 같이 물리적 순서를 맞추기 위한 작업이 필요하지 않다.
• 자료 구조의 크기를 통적으로 조정할 수 있어, 메모리의 효율적 사용이 가능하다.

구성요소

1. 노드
   • 연결 리스트에서 하나의 원소에 필요한 데이터를 갖고 있는 자료 단위
   • 구성
     a. 데이터 필드 : 원소의 값을 저장하는 자료구조, 저장할 원소의 종류나 크기에 따라 정의
     b. 링크 필드 : 다음 노드의 주소를 저장하는 자료구조

2. 헤드 : 리스트의 시작 위치에 해당하는 노드

헤드는 데이터가 필요 없이 다음 노드로 연결되는 것만 필요하다.

---

단순 연결 리스트 == 단방향 연결 리스트

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

구현 방법

1. 헤드를 첫 번째 데이터를 가지는 노드로 지정
   • 추가 연산을 할 때, 헤드가 null 값인지 확인 후 진행해야 한다.
2. 헤드가 빈 데이터를 가진 더미 노드
   • 헤드가 항상 고정이 될 수 있다. 데이터를 전부 삭제하더라도, 헤드노드는 남아있게 된다.
   • 추가 연산을 진행할 때, head 노드에 연결만 하면 되므로, 구현이 조금 더 쉽다.
   • 모든 연산을 중간 삭제, 중간 삽입으로 해도 된다.
   • 다만, 데이터가 삭제가 되어도, 헤드 노드 유지로 메모리 사용량이 늘어난다.

- 만약 A, C, D를 원소로 갖고 있는 리스트의 두 번째에 B노드를 삽입할 때 1. 우선 B노드를 새로운 노드로 생성 후 2. 새로운 노드 new의 데이터 필드에 'B'를 저장한다. 

바로 A와 B를 연결하게 되면, C와 D를 GarbageCollecter 에서 필요 없는 노드라 판단하여 삭제한다.
따라서 B가 C를 우선 연결하게 한 후 A와 B를 연결해준다.

• 노드를 삭제하는 경우
  

head가 빈 데이터를 갖는 경우, 찾기가 훨씬 쉽다.

자바 구현 예시

class Node{
	String data;
	Node link;
}

class SinglyLinkedList{
	Node head;
	int size;
	
	SinglyLinkedList(){
		head = new Node();
	}
	
	// 삽입 
	void addData(int i, String data) {
		//i 인덱스에 데이터 삽입 : 0이면 제일 앞에 추가, size와 동일하다면 제일 뒤에 추가 
		if (!(i > 0 || i > size)) {
			System.out.println("삽입할 위치가 잘못되었습니다.");
			return;
		}
		
		Node newnode = new Node();
		newnode.data = data;
		
		// 삽입할 위치 앞에 있는 노트 찾기 
		
		Node curr = head;
		
		for(int k = 0; k < i; k++) {
			curr = curr.link;  // 다음 노드 
		}
		
		// 새 노드부터 연결 
		newnode.link = curr.link; // 새 노드의 링크로 그 다음 노드를 링크 
		curr.link = newnode;
		
		size++;
	}
	
	
	// 삭제
	void removeData(int i) {
		if (!(i < 0 || i >= size)) {
			System.out.println("삭제할 위치가 잘못되었습니다.");
			return;
		}
		
		size--;
		
		// 삭제할 노드의 앞 노드로 이동 
		Node curr = head;
		
		for(int k = 0; k < i; k++) {
			curr = curr.link;
		}
		
		// 삭제할 노드의 앞 노드 link 가, 삭제할 노드 뒤의 노드와 연결되게 하는 것 
		curr.link = curr.link.link;
		
	}
	
	
	// 조회
	
	void printAll() {
		Node curr = head.link;
		
		while(curr != null) {
			System.out.print(curr.data + " -> ");
			curr = curr.link;
		}
		System.out.println();
	}
	
	
	// 데이터 개수 
}

---

---

이중 연결 리스트 == 양방향 연결 리스트

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

삽입

삭제

class DoublyLinkedList{
	Node head;
	Node tail; // 시작과 끝 위치를 나타내는 더미노드 
	
	int size;
	
	public DoublyLinkedList() {
		head = new Node();
		tail = new Node();
		
		head.next = tail;
		tail.prev = head;
	}
	
	void addData (int i, String data) {
		// 0 이라면 제일 앞에 삽입 
		// size 라면 제일 뒤에 삽입 
		if (i < 0 || i > size) {
			System.out.println("삽입이 불가능한 범위입니다.");
			return;
		}
		
		size++;
		
		// 삽입 위치 앞 노드를 찾는다. 
		Node curr = head;
		for (int k = 0; k < i; k++) {
			curr = curr.next;
		}
		
		// 새 노드 만들어주기 
		Node newnode = new Node();
		newnode.data = data;
		newnode.next = curr.next;
		newnode.prev = curr;
		
		
		// 기존 노드 연결 재구성 
		curr.prev.next = newnode;
        curr.next.prev = newnode;

	}
	
	void removeData (int i) {
		if(i < 0 || i > size) {
			System.out.println("삭제가 불가능한 범위입니다.");
		}
		
		size--;
		
		// 삭제할 위치 찾기 
		Node renode = head; 
		
		for(int k = 0; k <= i; k++) {
			renode = renode.next;
		}
		
		renode.prev.next = renode.next;
		renode.next.prev = renode.prev;
		
	}
	
	void printREverse() {
		
		Node curr = tail; 
		while (curr != head) {
			System.out.print("-- "+  curr.data);
		}
		
		System.out.println();
	}
		 
	
}