Developer_kade

• Tree
  • 그래프의 일종으로 하나의 노드는 여러개의 노드를 가리킬수 있지만 여러개의 노드가 하나의 노드를 가리킬수 없는 구조이다.
  • 노드와 노드를 이어주는 간선으로 구성되어있다.
  • 트리는 순회가 불가능 하다
  • 용어
    • Root Node : 최상의 부모 노드로서 하나만 존재한다
    • Parent Node : 부모노드, 0개 이상의 자식을 가질 수 있다.
    • child Node : 하나의 부모를 가진다.
    • Leaf Node : 자식이 없는 노드를 말한다.
    • edge : 간선, 노드와 노드를 연결하는 선을 말한다.
    • sibling : 간은 부모를 가지는 형제 노드
    • size : 자신을 포함한 모든 자식(자손)노드의 수
    • depth : 노드의 깊이(부모노드부터 하위 노드까지의 깊이)
    • level : 부모를 0으로 밑으로 내려갈수록 1씩 증가한다.
    • degree : 노드가 가지고있는 edge의 수
  • 
• 종류
  
  • binary : 부모노드가 자식노드를 최대 2개까지 가질 수 있다.
  • full binary : 모든 노드가 2개의 자식을 갖거나 자식이 없는 구조를 말한다.
  • perfect binary
    • 모든 내부 노드가 2개의 자식을 가지고 있어야 함
    • 모든 말단 노드(마지막 레벨에 하나의 노드만 있어서는 안됨)는 같은 높이에 있어야 함
  • ternary : 각 노드가 최대 3개의 자식을 갖는 트리
  • binary search
    • 부모 노드의 왼쪽 자식은 부모의 값보다 작은 값을 지닌 노드로 이루어져 있다.
    • 부모 노드의 오른쪽 자식은 부모의 값보다 큰 값을 지닌 노드로 이루어져 있다.
• Binary Search Tree 구현 코드
  • tree class생성

  • public class BinarySearchTree {
    	Node head = null;
    }​

     
  • 트리구조에서 데이터가 저장될 노드 클래스를 생성한다.

  • public class Node {
    	Node left;
        Node right;
        int data;
    
    	public Node(int data) {
        	this.data = data;
        }
    }

  • 삽입

  • public void add(int data) {
    	if(this.head == null) {
        	this.head = new Node(data);
        } else {
        	Node parentNode = this.head;
            
            while(true) {
            	if(data < parentNode.data) {
                	if(parentNode.left != null) {
                    	parentNode = parentNode.left;
                    } else {
                    	parentNode.left = new Node(data);
                        break;
                    }
                } else {
                	if(parentNode.right != null) {
                    	parentNode = parentNode.right;
                    } else {
                    	parentNode.right = new Node(data);
                        break;
                    }
                }
            }
        }
    }

  • 검색

  • public Node findNode(int data) {
    	if(this.head == null) {
        	return null;
        } else {
        	Node parentNode = this.haed;
            while(parentNode != null) {
            	if(parentNode.data == data) {
                	return parentNode;
                } else if(data < parentNode.data) {
                	parentNode = parentNode.left;
                } else {
                	parentNode = parentNode.right;
                }
            }
            return null;
        }
    }

  • 삭제

  • public Boolean remove(int data) {
    	Node currParentNode = this.head;
        Node currNode = this.head;
    
    	if (this.head == null) {
    		return false;
    	} else {
    		if (this.head.value == value && this.head.left == null && this.head.right == null) {
    			this.head = null;
    			return true;
    		}
    
    		while (currNode != null) {
    			if (currNode.value == value) {
    				searched = true;
    				break;
    			} else if (value < currNode.value) {
    				currParentNode = currNode;
    				currNode = currNode.left;
    			} else {
    				currParentNode = currNode;
    				currNode = currNode.right;
    			}
    		}
    
    		if (searched == false) {
    			return false;
    		}
    	}
    
    
    	if (currNode.left == null && currNode.right == null) {
    		if (value < currParentNode.value) {
    			currParentNode.left = null;
    			currNode = null;
    		} else {
    			currParentNode.right = null;
    			currNode = null;
    		}
    		return true;
    
    	} else if (currNode.left != null && currNode.right == null) {
    		if (value < currParentNode.value) {
    			currParentNode.left = currNode.left;
    			currNode = null;
    	} else {
    		currParentNode.right = currNode.left;
    		currNode = null;
    	}
    		return true;
    
    	} else if (currNode.left == null && currNode.right != null) {
    		if (value < currParentNode.value) {
    			currParentNode.left = currNode.right;
    			currNode = null;
    		} else {
    			currParentNode.right = currNode.right;
    			currNode = null;
    		}
    		return true;
    	} else {
    		if (value < currParentNode.value) {
    			Node changeNode = currNode.right;
    			Node changeParentNode = currNode.right;
    			while (currNode.left != null) {
    				changeParentNode = currNode;
    				changeNode = currNode.left;
    			}
    
    			if (changeNode.right != null) {
    				changeParentNode.left = changeNode.right;
    			} else {
    				changeParentNode.left = null;
    			}
    			changeNode.right = currNode.right;
    			changeNode.left = currNode.left;
    			currNode = null;
    		} else {
    			Node changeNode = currNode.right;
    			Node changeParentNode = currNode.right;
    			while (changeNode.left != null) {
    				changeParentNode = changeNode;
    				changeNode = changeNode.left;
    			}
    
    			if (changeNode.right != null) {
    				changeParentNode.left = changeNode.right;
    			} else {
    				changeParentNode.left = null;
    			}
    			currParentNode.right = changeNode;
    			changeNode.right = currNode.right;
    			changeNode.left = currNode.left;
    			currNode = null;
    		}
    		return true;
    	}
    }​

• Linked List
  • 연결 리스트, 링크드 리스트
  • 노드가 데이터와 포인터를 가지고 있고, 포인터는 다음 노드의 위치를 가지고 있는 구조이다.
  • Single Linked List는 다음 노드를 가리키는 하나의 포인터만 가지고 있다.
    • 
  • Double Linked List는 이전 노드와 다음 노드를 가리키는 포인터를 가지고 있다.
    • 

• 장점
  • 데이터의 삽입과 삭제가 용이하다.
  • 리스트 내에서 자료의 이동이 필요하지 않다.
  • 사용 후 기억 장소의 재사용이 가능하다.
• 단점
  • 포인터 사용으로 인한 저장공간의 낭비가 있다.
  • 알고리즘이 복잡하다.
  • 특정 자료의 탐색 시간이 많이 소요된다.

• 구현 코드(Single Linked List와 Double Linked List가 있지만 본 내용에서는 Double Linked List만 구현하겠다.)
• 어떤 데이터가 들어올지 모르기 때문에 제네릭으로 타입을 잡아서 클래스를 구현했다.
• 노드

  • public class Node<T> {
    	T data;
        Node<T> prev = null;
        Node<T> next = null;
        
        public Node(T data) {
        	this.data = data;
        }
    }

  • 위의 설명에서 Double Linked List의 노드는 앞, 뒤로 포인터를 갖는다고 했다.
  • 노드는 데이터를 가지고 prev로 앞의 노드를 세팅, next로 뒤의 노드를 세팅한다.
• Linked List 클래스 생성
  

  • public class DoubleLinkedList<T> {
    	Node<T> head = null;
        Node<T> tail = null;
    }

• 삽입 메소드 작성

  • public void add(T data) {
    	if(this.head == null) {
        	this.head = new Node<T>(data);
            this.tail = this.head;
        } else {
        	Node<T> node = this.head;
            while(node.next != null) {
            	node = node.next;
            }
            node.next = new Node<T>(data);
            node.next.prev = node;
            this.tail = node.next;
        }
    }

  • 해당 리스트의 head가 null이라면 리스트가 비어있다는 의미이기 때문에 바로 데이터를 삽입해 준다.
  • 이때 head와 tail에 모두 들어온 data를 담은 node를 넣어준다.
  • 만약 head가 null이 아니라면 이미 리스트에 자료가 있기 때문에 리스트를 순회하면서 포인터가 null을 가리키는 곳까지 가서 데이터 삽입 작업을 해준다.
  • node클래스를 보면 내부에 next 필드가 존재함으로 node의 next가 null이 나올 때까지 리스트를 순회하며 null값이 나온다면 그곳에 node를 세팅해 준 후 세팅한 노드의 prev의 포인터를 세팅해 준다.
  • 마지막으로 리스트의 tail을 세팅해준 마지막 노드로 바꿔주면 삽입작업이 끝나게 된다.
• 삭제

  • public Node<T> delete(T data) {
    	if(this.head != null) {
        	Node<T> node = this.head;
            while(node.next != null) {
            	if(node.data == data) {
                	Node<T> prev = node.prev;
                    Node<T> next = node.next;
                    
                    node.prev.next = next;
                    node.next.prev = prev;
                    
                    return node;
                } else {
    				node = node.next;
                }
            }
        }
        
        return null;
    }

  • head가 null이라면 리스트에 아무것도 없기때문에 null을 리턴해 준다.
  • head가 null이 아니라면 리스트를 순회하며 데이터가 같은 값인지를 확인한 후 같은 값이라면 이전 노드와 다음 노드를 연결해서 해당 노드를 끊어낸 후 해당 노드를 반환한다.
• 검색

  • public T frontSearch(T data) {
    	if(this.head != null) {
    		Node<T> node = this.head;
            while(node.next != null) {
            	if(node.data == data) {
                	return node.data;
                } else {
                	node = node.next;
                }
            }
        } 
        return null;
    }
    
    public T tailSearch(T data) {
    	if(this.head != null) {
        	Node<T> node = this.tail;
            while(node != null) {
            	if(node.data == data) {
                	return node.data;
                } else {
                	node = node.prev;
                }
            }
        }
        return null;
    }

  • 검색은 head 혹은 tail부터 검색을 할 수 있다.
  • head는 next를 사용해 순회하면 되고 tail은 prev를 사용해 순회하면 된다.

• Stack
  • 위키백과에는 '제한적으로 접근할 수 있는 나열 구조'라고 정의하고 있다.
  • 즉, 한쪽에서만 데이터의 입출력을 할 수 있다
  • 예를 들어서 집의 현관문을 생각해보면 현관문을 통해서만 밖으로 나가거나 집으로 들어올 수 있다.
  • 이와 같은 구조를 Stack이라고 부른다
  • LIFO(Last In First Out)구조라고 부른다.
  • 
• Code
  • 간단하게 구현한 코드이다
  • 편의상 오버플로우나 언더플로우는 작성하지 않았다
  • 큐와 다르게 remove시에 항상 마지막에 있는 값을 빼준다 

  • List<String> stack = new ArrayList<>();
    
    stack.add("A");
    stack.add("C");
    stack.add("D");
    stack.add("B");
    
    System.out.println(stack);
    // A C D B
    
    queue.remove(stack.size() - 1);
    // B out
    queue.remove(stack.size() - 1);
    // D out
    
    System.out.println(stack);
    // A C

• • Queue
    • 컴퓨터의 기본적인 자료구조이다
    • 터널과 같은 구조로 데이터가 들어가는 부분, 나오는 부분이 있다
    • 데이터가 들어간 순서대로 나온다.
    • FIFO(First In First Out) 구조라고 부른다
    • 
    • 위의 그림과 같이 1번이 제일 먼저 들어갔다면 1번이 제일 먼저 나오는 구조이다
  • Code
    • 간단하게 구현한 코드
    • 입력후 결과를 확인해 보면 입력한 순서대로 작동하는 것을 알 수 있다.
    • remove의 경우 큐의 특성대로 순서대로 데이터를 빼주면 된다 그러므로 리스트의 제일 앞 요소를 빼주면 되고 결과는 처음 넣은 A와 C가 리스트에서 빠져나오고 D와 B가 남은걸 확인할 수 있다. 

    • List<String> queue = new ArrayList<>();
      
      queue.add("A");
      queue.add("C");
      queue.add("D");
      queue.add("B");
      
      System.out.println(queue);
      // A C D B
      
      queue.remove(0);
      queue.remove(0);
      
      System.out.println(queue);
      // D B

• 데이터의 효율적인 접근 및 수정을 가능하게 하는 자료의 조직, 관리, 저장을 의미한다.

- 자료구조의 종류

• 선형 구조
  • 스택(Stack) : LIFO(Last In First Out) / 마지막에 들어간 값이 먼저 나오는 구조
  • 큐(Queue) : FIFO(First In First Out) / 처음 들어간 값이 처음 나오는 구조
  • 덱(Deque) : 큐와 스택을 합쳐놓은 것과 비슷하게 볼 수 있다. / 양쪽 끝에서 삽입과 삭제가 모두 가능한 구조
• 비선형 구조
  •  그래프(Graph) : 노드와 노드를 연결하는 간선을 하나로 모아놓은 자료구조
    • 
  •  트리(Tree) : 그래프의 한 종류로 여러 노드가 한 노드를 가리킬 수 없는 구조
    • 이진트리 : 자식 노드가 최대 두개인 트리구조 
      • 힙(Heap) : 이진트리의 일종으로 이진트리에 특성을 부여한 것(일반적으로 최댓값을 구하기 편하다)
    •