생활코딩 DataStructure -5

1. LinkedList 노드구현

 - LikedList는 내부적으로 Node라는 객체를 사용하여 Node와 Node를 연결한다(ArrayList는 내부적으로 배열을 이용) 

 - private class Node{ : 이너클래스 생성 , Node는 dayaType이 Node인 하나의 객체

 - private Object data; : 노드의 값

 - private Node next; : 다음 노드가 무엇인지 가르키기 위해 next의 dataType은 Node여야 한다.

 - public Node(Object input){ : 생성자를 이용해서 Node라는 객체가 이용될 때 객체를 초기화 한다. input : Node가 생성될때 어떠한 값을 갖고있어야 하는데, 그 값이 input이라고하는 생성자의 매개변수로 전달됨

 - this.data = input; : this.data는 현재 생성된 node의 값을 가르킴. (?this를 안하게 되면? node라는 객체를 공유하기 때문에 다른 data의 값이 변경되나?)

 - this.next = null; : 객체가 생성될 때는 next로 어떤 node가 올지 모르기 때문에 null로 지정.

 - return String.valueOf(this.data); : 디버그 등의 용도로 sysout으로 찍어볼 때 그 데이터 값을 알기위해 toString 정의

 

public class LinkedList {
	private Node head; 
	private Node tail; 
	private int size = 0;
	private class Node{ // 이너클래스 생성 , Node는 dayaType이 Node인 하나의 객체
		private Object data; 
		private Node next; 
		public Node(Object input){ 
			this.data = input; 
			this.next = null; 
		}
		public String toString() {
			return String.valueOf(this.data);
		}
	}

}

 

2. LiknedList Add구현

 

2-1 AddFirst

public void addFirst(Object input) {
	Node newNode = new Node(input);
	newNode.next = head; //각 노드는 다음값을 저장하고 있다!
	head = newNode;
    size++;
	if (head.next == null ) {
			tail = head;
	}
}

 

2-2 AddList

 

public void addLast(Object input) {
	Node newNode = new Node(input);
	if (size == 0) {
		addFirst(input);
	} else {
		tail.next = newNode;
		tail = newNode;
		size++;
	}
}

 

2-3 Add

 

	public void add(int index, Object input) {
		if (index == 0) {
			addFirst(input);
		} else {
			Node newNode = new Node(input); //temp2를 만들어서 지정하는 방식도 있지만, 그렇게하면 코드가 1줄 길어짐.
			Node temp1 = node(index-1); //node(index) 메서드를 사용하여, 새로추가할 newNode의 이전값을 temp1에 저장
			newNode.next = temp1.next;
			temp1.next = newNode;
			if (newNode.next == null) {
				tail = newNode;
			}
			size++;
		}
        
        
   public Node node(int index) { // 내부적으로 사용될 API 생성 (내부적으로 사용될 메서드를 public으로 선언하는 것은 바람직하지 않음, 단 test를 위해 public사용)
		Node x = head;
		for(int i = 0; i < index; i++) {
			x = x.next;
		}
		return x;
	} 

 

3. toString() 구현

	public String toString() {
		String str = "[";
		if (head == null) {
			str = "[]";
		} else str = str + head;
		Node i = head.next;
		while(i != null) {
			str = str + ", " + i;
			i = i.next;
		}
		return str + "]";
	}

 

 

4. removeFrist() 구현

 - LinkedList의 First값을 remove한 후, remove한 값을 리턴.

public Object removeFirst() {
		Node temp = head; //return할 값을 보존하기 위해, 기존 head를 삭제하기 전에 temp에 저장
		head = head.next;
		Object returnData = temp.data;
		temp = null;
		size--;
		return returnData;
	}

 

5. remove(int index) 구현

	public Object remove(int index) {
		if(index == 0) {
			return removeFirst();
		}
		Node temp = node(index-1); //삭제를 위해서는 지우고 싶은 값의 index의 이전값을 알야야 함.
		Node todoDeleted = temp.next; //삭제할 값을 todoDeleted에 저장하여, returnData 유지 
		temp.next = temp.next.next; //값의 연결이 끊어짐
		Object returnData = todoDeleted.data;
		if(todoDeleted == tail) { //지우고자하는 노드가 tail일 경우
			tail = temp; //이전 값을 tail로 설정한다. 
		}
		todoDeleted = null;
		size--;
		return returnData;
	}
	

 

6. removeLast() 구현 

 - tail값을 통해 Last노드를 삭제하지 않는 이유 : tail에 바로 접근을 할 수 없고, 다이렉트로 삭제한다 해도, 이전값을 tail로 설정해야 하기 때문에 결국 처음부터 링크를 타고 마지막까지 탐색한 후 삭제할 수 밖에 없음. 

	public Object returnLast() {
		return remove(size-1);
	}

 

 

7. size() , get(index) 구현 

 - size를 내부적으로 계속 유지하고 있기 때문에, return size를 통해 값을 가져올 수 있음.

	public int size() {
		return size;
	}
	
	public Object get(int index) { //해당 노드의 data를 가져옴 
		Node temp = node(index); 
		return temp.data;
	}

 

8. indexof(data)

 - 입력한 data의 index를 return하는 메서드

 - 마지막값이 정상 출력되게 수정하기!!!!!!

 

	public int indexOf(Object data) {
		Node temp = head;
		int index = 0;
		while(temp.data != data && temp != null) {
			temp = temp.next;
			index++;
		}
		if(temp.data != data) {
			return -1;
		} else return index;
	
	}
	

 

 

* 중요점

- tail, head 변수도 datatype이 node임