2014년 12월 17일 수요일

[자료 구조] 더블 링크드 리스트(Doubly Linked List)

자바 예제로 설명하는 더블 링크드 리스트(Singly Linked List)

더블 링크드 리스트란?

우선 시작하기 전에 잠시 싱글 링크드 리스트(단수 링크드 리스트) 이야기를 조금 해보자. 싱글 링크드 리스트에서 각각의 노드는 다음 노드의 주소만을 가지고 있기 때문에, 꼬리 노드, 즉 가장 마지막 노드를 제거하기 위해서 필수적으로 그 앞의 모든 노드들을 거쳐(Traverse)야 했다. 결국 싱글 링크드 리스트에서 removeTail 메소드는 O(n)의 효율성을 가질 수 밖에 없었다. 그렇니 잠시 이 구조를 어떻게 더 좋게 만들지 생각해 보자.  만약 각각의 노드가 자신의 전 노드(Predecessor Node) 와 다음 노드(Successor Node)의 주소를 모두 가지고 있다면 약간 더 많은 메모리를 쓰게 되지만 기능적으로는 더 효율적이지 않을까? 이게 바로 더블 링크드 리스트의 컨셉이다. 각각의 노드가 자신의 Predecessor Node와 Successor Node를 모두 참조한다는 것을 제외하고는 모든게 싱글 링크드 리스트(Singly Linked List)와 같다.

더블 링크드 리스트 예제
더블 링크드 리스트 예제

우리가 노드에 인터져만을 저장한다고 할 때 노드는 아래와 같이 구현된다.
아래는 자바 예제이다.

public class Node {
 public class Node {
 private int data;
 private Node predecessor, successor;

 public Node(int data) {
  this.data = data;
 }

 public Node(int data, Node predecessor, Node successor) {
  this.data = data;
  this.predecessor = predecessor;
  this.successor = successor;
 }

 public int getData() {
  return data;
 }

 public void setData(int data) {
  this.data = data;
 }

 public Node getPredecessor() {
  return predecessor;
 }

 public void setPredecessor(Node predecessor) {
  this.predecessor = predecessor;
 }

 public Node getSuccessor() {
  return successor;
 }

 public void setSuccessor(Node successor) {
  this.successor = successor;
 }
}


아래 표는 더블 링크드 리스트의 메소드들의 Big O 복잡도이다

Operation 이름Big O 복잡도
addHead(int t)O(1)
addTail(int t)O(1)
search(int t)O(n)
remove(int t)O(n)
removeHead()O(1)
removeTail()O(1)
clear()O(1)
isEmpty()O(1)

void addHead(int t)


더블 링크드 리스트 addHead 메소드
더블 링크드 리스트 addHead 메소드

이 메소드는 인터져 t 를 파라미터 값으로 받아 만든 새 노드를 리스트의 가장 첫번째 자리에 삽입한다
  1. head 인스턴스를 통해 첫번째 노드를 엑세스 한다.
  2. 새 노드의 successorNode 필드가 head instance 가 참조하는 첫번째 노드를 참조하도록 하게 한다
  3. head 인스턴스와 첫번째 노드간의 링크를 부수고 head 인스턴스가 새 노드를 참조게 한다.
아래는 자바로 구현된 addHead 메소드 이다

public void addhead(int t) {
  Node newNode = new Node(t);
  if (isEmpty()) {
   head = newNode;
   tail = head;
  } else {
   newNode.setSuccessor(head);
   head = newNode;
  }
 }


우선 파라미터로 받은 인터져 t 를 이용하여 새로운 노드 newNode 인스턴스를 생성한다. 그리고 리스트가 empty 상태인지 아닌지 확인한다. 만약 리스트가 empty 상태라면 우리는 head와 tail 인스턴스가 새로운 노드 newNode를 참조게 한다.
만약 리스트가 empty 상태가 아니라면, newNode의 successor 필드에 head 인스턴스가 참조하고 있는 첫번째 노드를 어싸인해준다. 그리고 head 인스턴스가 새 노드를 참조하게 만든다

void addTail(int t)


더블 링크드 리스트 addTail 메소드
더블 링크드 리스트 addTail 메소드

이 메소드는 주어진 인터져 t 로 만든 새로운 노드를 리스트의 가장 마지막 위치에 삽입한다
  1. tail 인스턴스를 통해 가장 마지막 노드에 엑세스 한후, 가장 마지막 노드의 successor 필드가 새로운 노드를 참조하게 한다
  2. 새 노드의 predecessor 필드가 마지막 노드를 참조하게 한다
  3. tail 인스턴스가 새로운 노드를 참조하게 만든다.

아래는 자바로 구현된 addTail 메소드 이다.

public void addTail(int t){
  Node newNode = new Node(t);
  if(isEmpty()){
   head = newNode;
   tail = head;
  }else{
   tail.setSuccessor(newNode);
   newNode.setPredecessor(tail);
   tail = newNode;
  }
 }


우선 우리는 주어진 인터져 t로 새로운 노드 newNode 인스턴스를 생성한다. 그리고 리스트가 empty 상태라면, head 와 tail 인스턴스가 newNode 인스턴스를 참조하게 만든다.
만약 리스트가 empty 상태가 아니라면, tail 인스턴스를 통해 마지막 노드의 successor 필드가newNode를 참조하게 만든다. 그리고 newNode의 predecessor 필드가 tail 인스턴스가 참조하는 노드, 즉 가장 마지막 노드를 참조하게 만든다. 그리고 tail 인스턴스가 새로운 노드인 newNode를 참조하게 만든다.

void removeHead()


더블 링크드 리스트 removeHead 메소드
더블 링크드 리스트 removeHead 메소드

이 메소드는 리스트의 가장 첫번째 노드를 삭제한다.
  1. head 인스턴스가 참조하는 첫번째 노드에 엑세스 한 후,  두번째 노드의 참조값을 얻어온다
  2. head 인스턴스가 두번째 노드를 참조하게 만든다.
  3. head 인스턴스를 통해 두번째 노드의 predecessor 필드를 null값으로 변경해, 원래의 첫번째 노드를 참조하는 인스턴스가 없게 만든다
  4. Java Garbage collector 가 첫번째 노드를 아무도 참조하지 않는것을 알아차렸으니, 이제 첫번째 노드에 할당된 메모리 영역은 다른 리소스들에게 할당될것이다
아래는 자바로 구현된 removeHead 메소드 이다.

public void removeHead() {
  if (head == tail) {
   clear();
  } else {
   head = head.getSuccessor();
   head.setPredecessor(null);
  }
 }


우선 우리는 head 와 tail 이 같은 값을 참조하는지를 확인한다, 만약 그렇다면 이는 head 와 tail 이 똑같은 null 값을 참조하거나 또는 같은 노드를 참조한다는것을, 즉 리스트에 노드가 1개 밖에 없다는걸 의미한다. 그렇므로 clear() 메소드를 이용해서 리스트의 내용을 모두 지워주면 된다
만약 그렇지 않다면, 우리는 getSuccessor 메소드를 이용해서 head 인스턴스가 두번째 노드를 참조하게 만든다. 그리고 setPredecessor 메소드를 이용하여 head 인스턴스가 참조하는 두번째 노드의 predecessor 필드를 null 값으로 설정한다. 이로써 원래의 첫번째를 참조하는 모든 인스턴스들이 수정됬고, java garbage collector가 곧 원래의 첫번째 노드에 할당된 메모리를 수거할것이다

void removeTail()


더블 링크드 리스트 removeTail 메소드
더블 링크드 리스트 removeTail 메소드

이 메소드는 리스트의 가장 마지막 노드를 제거한다
  1. 마지막 노드를 통해 마지막에서 2번째 노드의 참조값을 얻는다
  2. tail 인스턴스가 마지막에서 2번째 노드를 참조하게 하여, tail 인스턴스와 마지막 노드의 링크를 파괴한다
  3. 이제 수정된 tail 인스턴스가 참조하는 마지막에서 2번째 노드의 successor 필드가 null을 참조하게 하여 원래의 마지막 노드를 참조하는 인스턴스가 모두 없어졌다.
아래는 자바로 구현된 removeTail 메소드 이다

public void removeTail(){
  if(head==tail){
   clear();
  }else{
   tail = tail.getPredecessor();
   tail.setSuccessor(null);
  }
 }


우선 헤드와 테일 인스턴스가 일치하는지를 확인한다, 일치한다면 이는 리스트에 노드가 1개밖에 없거너 리스트가 empty 상태임을 의미한다. 그러니 그냥 clear 메소드를 이용해서 리스트를 비우자
만약 그렇지 안핟면, getPredecessor() 메소드를 이용, 뒤에서 두번째 노드에 엑세스 한후, tail 인스턴스가 뒤에서 두번째 노드를 가리키도록 만들자. 그리고 나서 바뀐 tail 인스턴스의 successor 필드를 null 로 해준다. 이로써 원래 마지막 노드가 리스트에서 삭제됬다

void remove(int t)


더블 링크드 리스트 remove 메소드
더블 링크드 리스트 remove 메소드

이 메소드는 인터져 t 를 가진 노드 중 가장 처음에 존재하는 노드를 제거하는 메소드 이다
우선 우리는 가장 첫 노드에서부터 모든 노드를 읽어(traverse) 목적 노드로 엑세스 해야한다.
그 후 아래와 같은 과정들을 거친다.
  1. 목적 노드의 successor 노드의 참조값을 얻는다
  2. 얻은 successor 노드의 참조값을 목적노드의 predecessor 노드의 successor 필드가 참조하게 한다.
  3. 목적 노드의 successor 노드의 predecessor 필드에 접근한다
  4. 접근한 predecessor 필드가 목적 노드의 predecessor 노드를 참조하게 한다
  5. 이제 목적노드를 참조하는 모든 인스턴스가 수정되었으니, 곧 java garbage collector 가 목적노드에 할당된 메모리를 수거하게 된다.
아래는 자바로 구현된 remove 메소드 이다.

public void remove(int t) {
  if (!isEmpty()) {
   if (head == tail && head.getData() == t) {
    clear();
   } else {
    Node pointer = head;
    while (pointer != null) {
     if (pointer.getSuccessor().getData() == t) {
      pointer.setSuccessor(pointer.getSuccessor().getSuccessor());
                                                pointer.getSuccessor().getSuccessor().setPredecessor(pointer);
      break;
     }
     pointer = pointer.getSuccessor();
    }
   }
  }
 }


우선 리스트가 empty상태인지 확인한다, empty 상태라면 제거할 노드가 없으니깐.
empty 상태가 아니라면 head 와 tail 인스턴스가 같은 노드를 참조하는지, 그 노드가 가진 인터져 값이 t 와 일치하는지를 확인한다, 만약 그렇다면 리스트에 1개밖에 없는 노드를 삭제해야되는 것이므로, clear 메소드를 이용해서 리스트를 클리어한다.
만약 아니라면, 와일(While) 루프를 이용해 pointer 인스턴스가 목적 노드의 successor 노드를 참조하게 한다. 그리고 그 successor 노드의 successor 필드가 목적 노드의 successor 노드를 참조하게 한다. 다음으로는, 목적 노드의 successor 노드의 predecessor 필드가 pointer 인스턴스가 참조하는 노드, 즉 목적노드의 predecessor 노드를 참조하게 한다. 그리고 break 구문을 이용해서 루프에서 탈출한다

아래는 자바로 구현된 clear 와 isEmpty 메소드 이다.

private void clear() {
  head = tail = null;
 }

 private boolean isEmpty() {
  if (head == null) {
   return true;
  } else {
   return false;
  }
 }

2014년 12월 15일 월요일

[자료 구조] 싱글 링크드 리스트(Singly Linked List)

자바 예제로 설명하는 싱글 링크드 리스트(Singly Linked List)

링크드 리스트(Linked List) 란?

Linked List 는 데이터와 다음 노드를 가리키는 주소를 가진 노드들의 배열로 이루어진 자료구조 이다. 즉 각각의 노드는 다른 노드를 참조하게 되어, 한 노드를 통해 다른 노드에 접근이 가능하다. 이로써 전체적으로 보았을때 각각의 노드는 첫노드와 끝노드를 잇는 체인(chain)을 구성하게 된다.

그렇다면 싱글 링크드 리스트(Singly Linked List)란?

우리는 각각의 노드들이 본인의 다음 노드의 주소만을 가지고 있을 때 그것을 Singly Linked List 라 한다.

싱글 링크드 리스트 예제
싱글 링크드 리스트 예제

위 그림을 보자. 각각의 노드들은 데이터와 다음 노드의 메모리 주소로 이루어져 있다. 그렇게 한 노드를 통해 다음 노드를 참조할 수 있게 되고, 결국에는 추상적인 배열을 이루게 된다. 추상적 배열이라 적은 이유는, 실제로 메모리 내에는 각각의 노드들이 제각각의 위치에 저장되기 때문이다.

링크드 리스트에는 Head와 Tail 이라 불리는 특별한 노드 인스턴스들이 존재하는데 이름에서 알 수 있듯이, Head 는 가장 첫 번째 노드를 가리키고 Tail 은 가장 마지막 노드를 가리킨다.

우리가 노드에 인터져 값을 저장한다 가정할 때, 그 Node 클래스는 아래와 같이 구현될것이다
아래는 Node 클래스의 자바 예제임

public class Node {
 private int data;
 private Node nextNode;
 
 public Node(int data) {
  this.data = data;
 }

 public Node(int data, Node nextNode) {  
  this.data = data;
  this.nextNode = nextNode;
 }

 public int getData() {
  return data;
 }

 public void setData(int data) {
  this.data = data;
 }

 public Node getNextNode() {
  return nextNode;
 }

 public void setNextNode(Node nextNode) {
  this.nextNode = nextNode;
 } 
}


아래는 싱글 링크드 리스트의 메소드들의 Big O 복잡도 이다
Operation 이름Big O 복잡도 
addHead(int t)O(1)
addTail(int t)O(1)
search(int t)O(n)
remove(int t)O(n)
removeHead()O(1)
removeTail()O(n)
clear()O(1)
isEmpty()O(1)

시작하기전에 SinglyLinkedList의 컨스트럭터와 인스턴스 변수들을 보고 가자.

public class SinglyLinkedList {
 private Node head, tail;

 public SinglyLinkedList() {
  head = null;
  tail = head;
 }
}


void addHead(int t)


싱글 링크드 리스트 addHead 메소드
싱글 링크드 리스트 addHead 메소드

이 메소드는 파라미터 값으로 주어진 인터져 t 를 이용해 새로운 노드를 만든 다음 리스트의 가장 첫번째 위치(Head)에 넣는다. Head라는 인스턴스로 가장 첫번째 노드의 레퍼런스를 가지고 있으므로 이 오퍼레이션은 O(1)의 Efficiency 로 실행 가능하다.
아래는 자바 예제이다

public void addHead(int t) {
  Node tmp = new Node(t, head);
  head = tmp;
  if (tail == null) {
   tail = head;
  }
 }


addHead 메소드는 인터져 t 를 파라미터로 받아, 데이터 값으로 t 를 가지고 다음 노드를 가리크는 레퍼런스 값으로 head의 주소를 가지는 새로운 노드 tmp 를 만들게 된다. 그리고 나서 우리는 head 값이 tmp 의 레퍼런스를 가리키게 만들게 된다. 그리고 tail 노드의 값이 만약 null 이라면, 이는 현재 리스트에 있는 노드의 수가 1개 밖에 없다는 것이니, tail 이 head를 가리키게 만든다.

void addTail(int t)


싱글 링크드 리스트 addTail 메소드
싱글 링크드 리스트 addTail 메소드

이 메소드는 파라미터 값으로 주어진 인터져 t 를 이용해 새로운 노드를 만든 다음 리스트의 가장 마지막 위치(Tail)에 넣는다. Tail라는 인스턴스로 가장 마지막 노드의 레퍼런스를 가지고 있으므로 이 오퍼레이션 또한 O(1)의 Efficiency 로 실행 가능하다.
아래는 자바 예제이다

public void addTail(int t) {
  Node tmp = new Node(t);
  if (isEmpty()) {
   head = tmp;
                        tail = head;
  } else {
   tail.setNextNode(tmp);
   tail = tail.getNextNode();
  }
 }


addHead 메소드와 같이, 우리는 주어진 인터져 t 로 새로운 노드 tmp 를 만들며 시작한다. 그리고 isEmpty 메소드를 이용해 리스트가 지금 empty 상태인지 확인한다. 만약 리스트가 텅 빈상태라면, 그져 새로운 노드를 head 인스턴스에 어싸인하고 tail 인스턴스가 head 인스턴스를 참조하게 만드는것이면 충분하다.
만약 리스트가 empty 상태가 아닐경우에, 우리는 우선 현재 tail 노드(곧 마지막에서 2번째 노드가 될 노드)의 다음노드로 tmp 노드를 참조케 한후, tail 인스턴스가 아까 어싸인한 tmp 노드를 참조하게 한다.

int search(int t)

이 오퍼레이션은 리스트에서 t 값을 가진 노드를 검색하여 그 중 가장 처음에 나오는 노드의 index 를 리턴하는 메소드 이다.

public int search(int t){
  Node pointer = head;
                int indexOfElement = -1;
                int traverseIndex = 0;
  while(pointer!=null)
  {
   if(pointer.getData()==t)
   {
    indexOfElement = traverseIndex;
    break;
   }
   pointer = pointer.getNextNode();
                        traverseIndex++;
  }
  return indexOfElement;
 }


정렬되지 않은 리스트에서 검색 작업은 언제나 모든 노드들을 읽는 작업 이다. 이는 Traverse 라 불리는데 그렇기 때문에, 언제나 O(n)의 efficiency 를 가진다.
우리는 우선 포인터로 쓸 노드를 만듬으로써 이 메소드를 시작해아한다. 만약
'head = head.getNextNode()'
라는 코드로 리스트를 traverse 해버리면 우리는 저 코드가 처음 실행되는 순간, 원래 head 의 위치를 잃어버리게 될것이고 결국 리스트는 엉망이 되어 버릴것이니다. 그렇니 traverse 작업중에 pointer 로 쓸 노드를 만들어 두고 시작하자.
우선 우리의 pointer 노드가 head와 같은 위치를 참조한 상태에서 시작한다. 그리고 looping을 하면서 우리가 원하는 값이 발견될 때까지, 발견되지 않는다면 리스트의 마지막 노드까지 traverse 작업을 하게 된다.

void removeHead()


싱글 링크드 리스트 removeHead 메소드
싱글 링크드 리스트 removeHead 메소드

이 메소드는 head 노드를 제거하고 head 인스턴스가 2번째 노드를 참조하게 만드는 메소드 이다.

public void removeHead() {
  if (head == tail) {
   clear();
  } else {
   head = head.getNextNode();
  }
 }


만약 head == tail 이라는 컨디션이 참이라면, 이는 리스트에 1개의 노드가 있거나 head 와 tail 이 둘다 null 임을 의미하니, 그냥 clear method 를 이용해서 리스트를 empty 상태로 만들어주면 된다.
만약 그렇지 않다면, 그냥 head의 다음 노드의 주소를 가져와, head 가 그 주소를 참조하도록 만들어야한다.

void removeTail()


싱글 링크드 리스트 removeTail 메소드
싱글 링크드 리스트 removeTail 메소드

이 메소드는 tail 인스턴스가 참조하는 가장 마지막 노드를 제거한다.

public void removeTail() {
  if (head == tail) {
   clear();
  } else {
   Node pointer = head;
   while (pointer.getNextNode() != tail) {
    pointer = pointer.getNextNode();
   }
   tail = pointer;
   tail.setNextNode(null);
  }
 }


Singly linked list 에서 전 노드에 엑세스할 방법은 head 에서부터 다시 traverse 하는 방법 뿐이다. removeHead 메소드와는 달리 이 작업을 완료하기 위해서는 tail 노드의 바로 전 노드의 reference 필드를 수정해야한다.
그렇기 때문에, 다시 pointer 노드를 이용해서 tail 노드의 바로 전 노드 까지 이동한다.
그리고 나서, pointer 노드 인스턴스가 참조하는 마지막에서 2번째 노드를 tail 인스턴스에 어싸인해준다. 그후에 tail.setNextNode(null) 메소드를 이용해서 원래 2번째 마지막 노드가 가지고 있는 마지막 노드의 주소 필드를 null 로 바꿔주면 끝~

void remove(int t)


싱글 링크드 리스트 remove 메소드
싱글 링크드 리스트 remove 메소드

이 메소드는 int t 값을 가진 노드 중 가장 앞에 존재하는 노드를 제거한다.

public void remove(int t) {
  if (!isEmpty()) {
   if (head == tail&&head.getData()==t) {
    clear();
   } else {
    Node pointer = head;
    while (pointer != null) {
     if (pointer.getNextNode().getData() == t) {
      pointer.setNextNode(pointer.getNextNode().getNextNode());
      break;
     }
     pointer = pointer.getNextNode();
    }
   }
  }
 }


첫번째로, 리스트가 Empty 상태인지 확인해야한다, 위 코드에는 나와있지 않지만 만약 Empty 상태이면 nullpointerexception 이나 다른 exception 을 던져야한다. 그리고 만약 empty 상태가 아니라면, 다음으로 head 와 tail 인스턴스가 같은 노드를 참조하고 있는지, 그리고 참조하는 노드의 데이터가 t 와 일치하는지를 비교한후, 일치한다면, 이는 리스트에 노드가 1개밖에 없다는 것이므로 clear 메소드를 이용해서 리스트를 empty 시킨다.
만약 그렇지 않다면 t 값을 가진 노드를 찾아서 리스트의 끝으로 traverse 하고, 노드를 찾았을 때 "pointer.setNextNode(pointer.getNextNode().getNextNode())".를 이용해서 노드가 참조하는 참조값을 수정하여 리스트에서 제거한다.

아래는 clear 메소드와 isEmpty 메소드를 자바로 구현한것이다.

private void clear() {
  head = tail = null;

 }

 private boolean isEmpty() {
  if (head == null) {
   return true;
  } else {
   return false;
  }
 }

2014년 12월 6일 토요일

[UML] Class Diagram [클래스 다이어그램]

Class Diagram(클래스 다이어그램) 예제


UML 클래스 다이어그램 예제
UML 클래스 다이어그램 예제

Class Diagram은 소프트웨어의 정적 요소인 클래스들간의 관계를 보여주는 Structure Diagram이다.

2014년 12월 5일 금요일

[UML] 통합 모델링 언어 [UML(Unified Modelling Language)] 이란

통압 모델링 언어(Unified  Modelling Language<UML>)은 소프트웨어 설계 단계에서 쓰이는 모델링 언어로, 소프트웨어의 구조를 시각적으로 표현하는 언어이다. 1994년 Grady Booch, Ivar Jacobson 그리고 James Rumbaugh들에 의해 Rational Software 에서 개발되었으며, 1997년 객체 관리 그룹(Object Management Group<OMG>)에 의해 표준 모델링 언어로 선정 되었으며, 2000년에는 국제 표준화 기구(International Organization for Standardization<ISO>)에 의해 국제 표준으로 선정되었다.

UML을 이용한 UML Diagram 에는 여러가지 종류가 있는데, 모두 각각 소프트웨어의 정적(Static)요소들 또는 동적(Dynamic)요소들을 표현한다.


UML Diagram Overview : http://en.wikipedia.org/wiki/File:UML_diagrams_overview.svg