자료구조: 1-2 단방향 연결리스트 구현

참 ... 복잡하다... 연결리스트...
하지만 하나하나 뜯어보면, 코드를 통째로 이해할 수 있을 것이다.

public class SingleLinkedList {
	Node head;
	int size = 0;
	
	Node findNode(int searchIdx) {
		//1. 찾는 노드의 index가 음수거나 사이즈보다 크면 예외 발생
		//2. 노드 탐색: 위치의 인덱스와 같아질 때까지 루프 탐색
		if (searchIdx < 0 || searchIdx >= size) {
			throw new ArrayIndexOutOfBoundsException();
		}
		
		Node pointer = head;
		int nowIdx = 0;
		
		while(searchIdx != nowIdx) {
			++nowIdx;
			pointer = pointer.next;
		}
		
		return pointer;
	}
	
	Object getData(int searchIdx) {
		//findNode활용해서 데이터만 가져오기 뾱-
		return this.findNode(searchIdx).data;
	}
	
	boolean isEmpty() {
		//노드가 아예 없는건가? 라고 물어봄. ㅇㅇ
		return 0 == size;
	}
	
	int size() {
		//노드가 몇개있니? 라고 물어봄 ㅇㅇ
		return size;
	}
	
	void addLast(Object data) {
		//add메소드 써서 마지막 노드에 데이터 추가
		this.add(size, data);
	}
	
	void addFirst(Object data) {	
		//add 메소드 써서 첫번째 노드로 추가
		this.add(0, data);
	}
	
	void removeLast() {
		//마지막 노드 삭제. remove 메소드 사용
		this.remove(size-1);
	}
	
	void removeFirst() {
		//첫번째 노드 삭제. remove 메소드 사용
		this.remove(0);
	}
	
	void getHeadInfo() {
		System.out.println(head.data);
		System.out.println(head.next);
	}
	
	void add(int index, Object data) {
		//1. 노드 껍데기 하나 만들고, 데이터 칸에 입력된 데이터 넣기.
		Node newNode = new Node();
		newNode.data = data;
		//2. 맨 앞에 넣는 경우, 그게 아닌 경우 구분해서 조건문 작성해야함.
		if (0 == index) {
			newNode.next = head;
			head = newNode;
		} else {
			Node foundNode = this.findNode(index - 1);
			newNode.next = foundNode.next; //뒷 노드와 연결
			foundNode.next = newNode; //앞 노드와 연결
		}
		++size;
	}
	
	void remove(int index) {
		//인덱스가 0이거나 head가 null이 아니면 첫 노드 삭제
		if (index == 0 && head != null) {
			head = head.next ;
		} else {
			//삭제하려는 노드의 이전 노드와 다음 노드를 연결
			Node prevNode = this.findNode(index-1);
			prevNode.next = prevNode.next.next;
		}
		--size;
	}

	@Override
	public String toString() {
		// TODO Auto-generated method stub
		//출력 돕는 도구 ㅇㅇ
		StringBuilder sb = new StringBuilder();
		Node pointer = head;
		sb.append("head").append(" -> ");
		while(pointer != null) {
			sb.append(pointer.data).append(" -> ");
			pointer = pointer.next;
		}
		sb.append("null");
		return sb.toString();
	}

우선 구현을 위한 소스코드는 100줄 가량 필요하다.
막막해 보이지만, 기능 단위로 뜯어보면 이해할 수 있다.
주요 기능은 아래와 같다.

• 삽입() 함수 -> 삽입 위치에 따른 제어문 구현 필요
• 노드찾기() 함수
• 삭제() 함수 -> 삭제 위치에 따른 제어문 구현 필요
• 연결리스트가 비어있니() 함수
• 연결리스트의 크기가 얼마나되니() 함수

1. 삽입() 함수

노드 삽입은 첫번째 위치 삽입과 중간 위치 삽입으로 구분된다.

• 최초 및 첫번째 위치 삽입
  

  네모 1> 최초에 노드를 삽입할 땐, head는 null값으로 저장되어 있을 것이다. 이때 새로운 노드가 삽입하려고 할 땐, 새로운 노드의 next 영역을 현재 head에 저장된 null값으로 채워넣고, head엔 삽입할 노드의 주소를 저장하면 된다.

네모 2> 최초 삽입이 아닌데, 첫번째 위치에 노드를 넣는 경우도 마찬가지이다. head에 저장된 원래 첫번째 노드의 주소값을 새로운 노드의 next영역에 저장한다. 그리고 head엔 새로운 노드의 주소 값을 넣어주면 된다.
(구현 편의상 head는 첫번째 노드의 복사본이라고 퉁칩시다.)

• 중간 위치 삽입
  

  원리는 첫번째 노드 삽입과 유사하다. 우선 삽입할 위치까지 이동하고, 찾은 노드의 다음 노드의 주소값을 새로운 노드의 next 영역에 저장한다. 그 후 새로운 노드는 찾은 노드의 next 영역에 할당된다. 구현 코드는 아래와 같다.

	void add(int index, Object data) {
		//1. 노드 껍데기 하나 만들고, 데이터 칸에 입력된 데이터 넣기.
		Node newNode = new Node();
		newNode.data = data;
		//2. 맨 앞에 넣는 경우, 그게 아닌 경우 구분해서 조건문 작성해야함.
		if (0 == index) {
			newNode.next = head;
			head = newNode;
		} else {
			Node foundNode = this.findNode(index - 1);
			newNode.next = foundNode.next; //뒷 노드와 연결
			foundNode.next = newNode; //앞 노드와 연결
		}
        //리스트 크기 +1
		++size;
	}

2. 삭제 함수

삭제할 때도 마찬가지로, 삭제 위치에 따라 구현 방식이 조금씩 달라진다.

그림의 네모 1>은 첫 번째 노드 삭제이고, 네모 2>는 중간 노드 삭제 예시이다.

네모 1> 너무 단순하다. 그저 head를 삭제하려는 노드의 다음 번에 있는 노드의 주소 값으로 바꿔놓으면 된다. 삭제 노드는 자연스레 가비지 컬렉터가 수거해간다.

네모 2> 조금 복잡하다. 하지만 삭제 위치까지 이동한 후, 삭제 위치의 이전 노드와 이후 노드를 연결하면 된다. 삭제 위치의 이전 노드의 next 영역에 삭제 위치 이후 노드의 주소값을 채워넣으면 끝이다.

구현 코드는 아래와 같다.

	void remove(int index) {
		//인덱스가 0이거나 head가 null이 아니면 첫 노드 삭제
		if (index == 0 && head != null) {
			head = head.next ;
		} else {
			//삭제하려는 노드의 이전 노드와 다음 노드를 연결
			Node prevNode = this.findNode(index-1);
			prevNode.next = prevNode.next.next;
		}
        //리스트 크기 -1
		--size;
	}

3. 노드찾기() 함수

노드 찾기는 포인터라는 임의의 변수의 도움이 필요하다.
포인터는 특정 위치의 노드를 임시로 저장하는 변수이다.

찾을 위치를 매개변수로 받고, 포인터를 이동시키면 된다.
0으로 초기화된 카운팅 변수를 하나 생성하고, 찾는 노드가 나올 때까지 값을 +1 시킨다. 그리고 카운팅 변수가 매개변수의 값과 일치하면, pointer에 값을 복사해서 함수를 반환하면 된다.

	Node findNode(int searchIdx) {
		//1. 찾는 노드의 index가 음수거나 사이즈보다 크면 예외 발생
		//2. 노드 탐색: 위치의 인덱스와 같아질 때까지 루프 탐색
		if (searchIdx < 0 || searchIdx >= size) {
			throw new ArrayIndexOutOfBoundsException();
		}
		
		Node pointer = head;
		int counter = 0;
		
		while(searchIdx != counter) {
			++counter;
			pointer = pointer.next;
		}
		
		return pointer;
	}

3. 연결리스트가 비어있니 함수()
   음... 굳이 설명이 필요 없을 만큼 간단하다. 그저 class 선언 시 인스턴스 변수로 선언한 size 변수가 0인지 체크해서 boolean 타입으로 값을 반환하면 된다.

	boolean isEmpty() {
		//노드가 아예 없는건가? 라고 물어봄. ㅇㅇ
		return 0 == size;
	}

4. 연결리스트의 크기가 얼마나 되니() 함수
   역시 단순하다. 그냥 size 인스턴스 변수 값을 반환하면 된다.

	int size() {
		//노드가 몇개있니? 라고 물어봄 ㅇㅇ
		return size;
	}

5. 정리

처음 코드를 봤을 땐, 이게 무슨 소리인지 모를 수 있다.
하지만 기능 단위로 코드를 뜯어보고 , 왜 이렇게 동작하는지 이해한다면 100줄의 구현코드를 한 번에 이해할 수 있을 것이다.
코드를 단순화하면 아래와 같다.

class 연결리스트 {
	1.인스턴스 변수 (size(정수 0 초기화), head(null로 초기화))
    	2.필요한 함수
        add(index, data), remove(index), 
        findNode(index), size(), isEmpty()
        3. 부가기능 함수
        addFirst(첫번째 위치 삽입), addLast(중간 위치 삽입), 
        removeFirst(첫째 원소 삭제), removeLast(중간 원소 삭제),
        getData(찾은 원소의 data영역 값 리턴)...
    
}