레이블이 자료 구조인 게시물을 표시합니다. 모든 게시물 표시
레이블이 자료 구조인 게시물을 표시합니다. 모든 게시물 표시

2015년 1월 11일 일요일

[자료 구조] 힙(Heap)

자바(Java)예제로 구현한 힙(Heap) 자료 구조

힙(Heap) 이란 무었인가?

힙(Heap)은 완전 이진 트리(Complete Binary Tree)로, 각각의 노드가 자신의 부모 노드보다 작거나 같은 값을 저장하는 자료형 이다. 힙(Heap)은 완전 이진 트리(Complete Binary Tree)라 가장 아래에 있는 노드들을 제외한 모든 노드들이 두 자식 노드를 모두 가지고 있거나 아예 자식 노드를 가지지 않는 특성을 가진다.
  • 만약 부모 노드가 자식 노드보다 크거나 같다면 그건 "Max Heap"(최대 힙)
  • 부모 노드가 자식 노드보다 작거나 같다면 "Min Heap"(최소 힙) 이라 불린다.
힙(Heap) 컨셉
힙(Heap) 컨셉

힙(Heap)은 실제로 어디에 사용될까?

  • Heapsort(힙 정렬)
  • 우선 순위 큐(Priority Queue)
    • 힙 자료 구조는 우선 순위 큐를 구현하는데 많이 쓰인다
  • 다양한 알고리즘(Algorithm) 구현

이진 힙(Binary Heap) 은 어떻게 구현되는가?

추상 자료형인 힙(Heap)은 매우 다양한 방법으로 구현될 수 있다. 가장 대중적인 힙 구현 방법은 Array를 이용하는 것이다. 우선 아래의 Big O 복잡도 표를 보고 가자

OperationBig O Complexity
InsertO(log n)
Remove MaxO(log n)
Fix RootO(log n)

*중요한건, Array 를 이용한 이진 트리 구현에서, 인덱스 i 에 저장된 부모 노드의 두 자식 노드는 인덱스 (2*i)+1 와 (2*i)+2에 저장된다는걸 기억하자.

아래는 자바 배열(array)로 구현한 힙(Heap) 자료 구조 이다.


public class Heap {
 private int[] data;
 private int size;
 private int maximumSize;

 public Heap() {
  data = new int[100];
 }

 public static void main(String[] args) {
  int[] arr = new int[5];
  for (int i : arr) {
   System.out.println(i);
  }
 }

 public Heap(int maximumSize) {
  if (maximumSize < 1) {
   this.maximumSize = 100;
  } else {
   this.maximumSize = maximumSize;
  }
  this.maximumSize = maximumSize;
 }

 public boolean isEmpty() {
  return size == 0;
 }

 public boolean isFull() {
  return size == 100;
 }

 public void clear() {
  data = null;
 }

 // 새로운 데이터를 삽입
 public void insert(int newInt) {
  int pointer;// 어레이의 인덱스를 가리키는 포인터 이다.
  if (isFull()) {
   throw new FullHeapException();
   // 힙이 꽉 차있다면 Exception(예외) 처리를 해주자
  } else {
   // 아니면 배열의 끝에 새로운 데이터를 삽입한다.
   data[size] = newInt;
   pointer = size;
   size++;

   while (pointer > 0 && data[pointer] > data[(pointer - 1) / 2]) {
    // 최대 힙에서 자식 노드는 무조건 부모 노드보다 작거나 같아야한다
    // 그러니 끝에 삽입된 노드를 부모 노드와 비교해서 크다면 부모 노드와 교체해주자
    int temp = data[pointer];
    data[pointer] = data[(pointer - 1) / 2];
    data[(pointer - 1) / 2] = temp;
    pointer = (pointer - 1) / 2;
   }
  }
 }
 
 // 힙에서 노드를 제거
 // 힙에서 제거 메소드는 가장 큰 노드 1개, 즉 루트 노드를 제거하고 반환한다.
 public int remove() {
  int toReturn;//리턴될 인스턴스
  if (!isEmpty()) {
   toReturn = data[0];
   // 어레이의 가장 끝에 존재하는 노드를 루트 노드에 집어넣는다
   data[0] = data[--size];
   data[size] = 0;
  } else {
   // 만약 힙이 텅 빈 상태라면 예외 처리를 해주자
   throw new EmptyHeapException();
  }

  // 어레이의 가장 끝에 있는 노드를 루트 노드에 넣었으니, 힙을 재정렬 해야한다.
  fixRoot();//재정렬 메소드를 실행하자

  return toReturn;//toReturn 인스턴스에 저장된 값을 반환한다.

 }

 public void fixRoot() {
  // remove 메소드에서 가장 큰 노드,즉 루트 노드를 제거하고 그 자리에 가장 끝에 있는 노드를 삽입했다.
  // 다시 힙을 재정렬 함으로써 루트 노드가 적절값을 가지도록 해야한다.

  int pointer = 0;//루트 노드에서 시작한다
  while (pointer * 2 + 1 < size) {
   // 자식 노드중 더 큰 노드와 자리를 교체한다.
   if (data[pointer * 2 + 1] > data[pointer * 2 + 2]) {
    int temp = data[pointer];
    data[pointer] = data[pointer * 2 + 1];
    data[pointer * 2 + 1] = temp;
    pointer = pointer * 2 + 1;
   } else {
    int temp = data[pointer];
    data[pointer] = data[pointer * 2 + 2];
    data[pointer * 2 + 2] = temp;
    pointer = pointer * 2 + 2;
   }
  }
 }
}

2015년 1월 10일 토요일

[자료 구조] 이진 탐색 트리 (Binary Search Tree(BST))

자바 예제로 설명하는 이진 탐색 트리 (Binary Search Tree(BST))


이진 탐색 트리 예제
이진 탐색 트리 예제

이진 탐색 트리 (Binary Search Tree(BST)) 란?

이진 탐색 트리는 트리 자료 구조의 종류 중 1개로써, 각 노드가 최대 2개의 자식(Child) 노드를 가질 수 있는 트리이다. 이진 탐색 트리에서 새로운 노드는 루트 노드부터 비교를 거쳐, 비교된 노드 보다 더 크면 오른쪽 서브 트리로 이동하고, 작으면 왼쪽 서브 트리로 이동해서 계속 크기 비교 후, 알맞은 자리에 삽입된다. 위의 그림에서 3이라는 노드가 삽입될 때, 우선 루트 노드인 33 과 비교 후, 22와 비교 후, 22의 왼쪽 자식 노드로 삽입되는 것 이다.

이러한 특징 덕분에, 이진 탐색 트리(Binary Search Tree)를 중위 순회(Inorder Traversal)로 순회하게 되면, 정렬된 값을 읽을 수 있다. 위의 예제를 Inorder Traversal 로 순회한다면
[3, 22, 26, 33, 44 55, 77]
이 된다

이진 탐색 트리(Binary Search Tree) 는 어디에 쓰일까?

  • 이진 암호화
  • 데이터 베이스
  • 파일 시스템

이진 탐색 트리(Binary Search Tree)는 어떻게 구현되는가?

이진 트리는 추상 자료형이다, 이는 즉 매우 다양한 방법으로 구현될 수 있음을 의미한다. 보통 가장 자주 쓰이는 방법은 싱글 링크드 리스트(Singly Linked List)이다. 우선 아래에 적힌 이진 탐색트리의 Big O 복잡도를 보고 가자.

Operation Big O Complexity
Average Worst
InsertO(log n)O(n)
DeleteO(log n)O(n)
SearchO(log n)O(n)

큐(Queue)나 스택(Stack)과 같은 선형 자료 구조들과는 달리, 비선형 자료 구조에서 각각의 오퍼레이션들은 평균(Average)와 최악(Worst) 케이스이라는 두가지 케이스의 Big O 복잡도를 가진다. 이진 탐색 트리(Binary Search Tree)의 경우에 Average(평균) 케이스란 균형이 잘 맞는(Well-Balanced) 트리를 말하며, 최악의 케이스란 아래의 그림과 같은 형태를 띄어 선형 자료 구조와 다른게 없는 상황을 말한다. 아래 그림 예제를 보자.

이진 탐색 트리 최악의 경우
이진 탐색 트리 최악의 경우

만약 우리가 이진 탐색 트리에 데이터를 33,22,3 순으로 삽입하면, 위의 그림과 같은 구조를 볼 수 있을 것 이다. 이럴 경우에 이진 탐색 트리는 싱글 링크드 리스트와 완전 일치하며, 비선형 자료 구조의 장점을 잃게 된다.

이진 탐색 트리(Binary Search Tree), 왜 중복 노드를 가져서는 안되는걸까?

아래의 자바(Java) 예제 코드를 보면 알겠지만, 이진 탐색 트리(Binary Search Tree)는 매우 직관적이고 단순한 검색 알고리즘을 가지고 있다. 이진 탐색 트리에서 새로운 노드가 더 부모 노드보다 더 크면, 그 노드는 오른쪽에 위치하게 되고, 작으면 왼쪽에 위치하게 된다. 이러한 특성 때문에, 검색 알고리즘은 검색 쿼리와 노드 값을 비교해가며 노드의 위치를 찾아간다.

만약 중복값을 가진 노드가 존재한다 가정할 때, 우리는 두 가지 검색 알고리즘을 만들 수 있을것이다.

첫번째로, 우선 발견되는 노드만 신경쓰고, 중복 노드가 존재할 가능성을 무시하는것이다. 이 경우에 이진 탐색 트리(Binary Search Tree)는 아무런 쓸모가 없고 사용되지 않을 노드를 가지게 되는 것 이고, 결국에 이는 메모리 낭비에 불과하다.

두번째 경우는, 우리가 중복되는 모든 노드를 검색하는 것 이다. 이 경우에 우리 검색 알고리즘은 언제나 중복 노드가 존재한다는 가정을 할 것이고, 결국 모든 중복 노드를 찾기 위해서 언제나 잎(Leaf) 노드, 즉 최 하위 노드까지 검색을 이어가야 하는 그리 좋지 않은 시나리오를 가질 것이다

그렇니, 효율성(Efficiency)을 위해, 특이한 상황이 아니라면 트리는 중복 노드를 가지지 않는다.

아래 코드는 노드(Node) 클래스의 자바(Java) 예제 이다.

public class Node {
public class Node {
 private Node left, right;
 private int data;

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

 /**
  * 현재 노드에서 중위 순회(inOrder Traversal)을 시작한다.
  */
 public void inOrder() {
  // 회귀 함수(Recursive Call)을 이용, 가장 왼쪽 노드로 이동한다.
  if (left != null) {
   left.preOrder();
  }
  // 그리고 노드를 읽는다.
  System.out.println(data);
  // 그 후 다시 회귀 함수(Recursive Call)을 이용 오른쪽 노드를 읽는다.
  if (right != null) {
   right.preOrder();
  }
 }

 /**
  * 현재 노드에서 전위 순회(PreOrder Traversal)을 시작한다
  */
 public void preOrder() {
  // 현재 노드를 읽는다
  System.out.println(data);
  // 그후 회귀 함수(Recursive Call)을 이용
  // 가장 왼쪽 잎(Leaf)노드로 이동.
  if (left != null) {
   left.preOrder();
  }
  // 그 후 오른쪽 노드를 탐색한다.
  if (right != null) {
   right.preOrder();
  }
 }

 /**
  * 현재 노드에서 후위 순회(PostOrder Traversal)을 시작한다
  */
 public void postOrder() {

  if (left != null) {
   left.postOrder();
  }

  if (right != null) {
   right.postOrder();
  }
  System.out.println(data);
 }

 public Node getLeft() {
  return left;
 }

 public void setLeft(Node left) {
  this.left = left;
 }

 public Node getRight() {
  return right;
 }

 public void setRight(Node right) {
  this.right = right;
 }

 public int getData() {
  return data;
 }

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

}


아래 코드는 이진 탐색 트리(Binary Search Tree) 클래스의 자바 예제 이다.

public class BinarySearchTree {
 private Node root;// 루트 노드 인스턴스 생성

 // 이진 탐색 트리 생성자
 public BinarySearchTree() {
  root = null;
 }

 public boolean isEmpty() {
  return root == null;
 }

 public void clear() {
  root = null;
 }

 public void inOrder() {
  root.inOrder();
 }

 public void preOrder() {
  root.preOrder();
 }

 public void postOrder() {
  root.postOrder();
 }

 /**
  * 주어진 인터져 t 로 새로운 노드를 생성, 삽입한다
  * 
  * @param 삽입할 인터져 t
  * @return 삽입이 성공하면 true 갑을, 실패하면 false 값을 리턴
  */
 public boolean insert(int t) {
  Node newNode = new Node(t);// 주어진 인터져 t 로 새 노드를 생성
  Node pointer;// 노드를 삽입할 위치까지 트리를 순회해야하니, 포인터 인스턴스를 생성한다
  boolean insertComplete = false;
  if (root == null) {
   // 트리가 empty 상태일 경우, 루트 노드에 삽입
   root = newNode;
  } else {
   pointer = root;
   // while 루프로 순회를 시작한다.
   while (!insertComplete) {
    if (pointer.getData() > t) {
     // 인터져 t 를 각 노드들과 비교하여, 작으면 
     // 왼쪽 자식으로, 크면 오른쪽 자식으로 이동한다
     if (pointer.getLeft() != null) {
      pointer = pointer.getLeft();
     } else {
      pointer.setLeft(newNode);
      insertComplete = true;
      break;
      // 노드 삽입이 완료됬다면, 더이상의 루핑은 불필요하다.
      // break 구문을 이용, 루프를 종료하자
     }
    } else if (pointer.getData() < t) {
     if (pointer.getRight() != null) {
      pointer = pointer.getRight();
     } else {
      pointer.setRight(newNode);
      insertComplete = true;
      break;
     }
    } else {
     // 만약 트리에 이미 중복되는 노드가 존재한다면
     // 삽입은 불필요하다. 그러니 루핑을 종료한다
     break;
    }
   }
  }
  // 삽입이 성공적이라면 true 값을
  // 중복 노드가 존재한다거나, 예상외 상황이 있어서 삽입을 실패했다면 false 값을 반환한다.
  return insertComplete;
 }

 /**
  * 인터져 t 를 가진 노드를 트리에서 제거한다
  * 
  * @param t 제거할 값 인터져 t
  * @return 성공적으로 제거했을 때 true 값을, 실패했을 때 false 값을 리턴한다
  */
 public boolean remove(int t) {
  Node pointer, parentPointer;
  pointer = parentPointer = root;
  while (pointer != null && pointer.getData() != t) {
   // 삭제할 노드를 찾을 때까지 루핑으로 트리를 순회한다
   parentPointer = pointer;// parentPointer 인스턴스가 삭제할 노드의 부모 노드를 참조하도록 한다.
   if (pointer.getData() > t) {
    pointer = pointer.getLeft();
   } else {
    pointer = pointer.getRight();
   }
  }

  if (pointer == null) {
   // 첫번째 상황: 트리에 삭제할 노드가 존재하지 않을때
   return false;
  } else {
   if (pointer == root && pointer.getLeft() == null) {
    // 두번째 상황: 제거할 노드가 루트 노드이고, 루트노드가 왼쪽 자식 노드를 가지지 않을 때
    root = root.getRight();
   } else if (pointer != root && pointer.getLeft() == null) {
    // 세번째 상황: 루트 노드가 아닌 제거할 노드가 왼쪽 자식 노드를 가지지 않을 때
    if (pointer == parentPointer.getLeft()) {
     // 제거할 노드가 부모 노드의 왼쪽에 위치할 때
     parentPointer.setLeft(pointer.getRight());
    } else {
     // 제거할 노드가 부모 노드의 오른쪽에 위치할 때
     parentPointer.setRight(pointer.getRight());
    }
   } else {
    // 네번째 상황: 제거할 노드가 2개의 자식 노드 모두를 가지고 있을 때
    // 이러한 상황에서 우리는 제거할 노드에서 파생된 서브 트리에서 가장 큰 노드를 검색한 후, 
    // 제거할 노드의 위치에 삽입할 것 이다.
    // BST에서 가장 오른쪽에 위치한 노드는 가장 큰 값을 가졌다는걸 기억하자.
    // 그러니 BST의 왼쪽 서브 트리의 가장 오른쪽에 존재하는 잎(Leaf)노드는 루트 노드의 가장 좋은 대체제 이다.
    Node rightMostNode = pointer;
    // while 루핑을 이용해서 가장 오른쪽 노드로 이동하자
    while (rightMostNode.getRight() != null) {
     rightMostNode = rightMostNode.getRight();
    }
    // 제거할 노드의 데이터 값을 가장 오른쪽 노드의 데이터 값으로 바꿔주자
    pointer.setData(rightMostNode.getData());
    rightMostNode = null;// 오른쪽 노드를 null로 만든다
   }
  }
  return true;
 }

 /**
  * 인터져 t 값을 가진 노드를 검색한다
  * 
  * @param t 검색할 인터져 t
  * @return 존재한다면 true 값을, 그렇지 않다면 false 값을 반환한다.
  */
 public boolean serach(int t) {
  Node pointer;
  if (root.getData() == t) {
   // 루트 노드가 값을 가지고 있는지 확인
   return true;
  } else {
   // 값을 찾을 때 까지 트리를 순회하자
   pointer = root;
   while (pointer != null) {
    if (pointer.getData() > t) {
     pointer = pointer.getLeft();
    } else if (pointer.getData() < t) {
     pointer = pointer.getRight();
    } else {
     // 인터져 t가 노드와 비교 했을 때 크지도 작지도 않다면, 이는 값이 일치함을 말한다. 
     // 루핑을 종료한다
     break;
    }
   }
  }
  // 만약 트리에 인터져 t 값을 가진 노드가 존재하지 않는다면
  // 위의 while 루프에서 트리의 끝까지 여행하게 될거고, 결국 pointer 인스턴스는 null 값을 참조하게 될 것 이다
  // 하지만 트리에 t값을 가진 노드가 존재한다면, pointer 인스턴스는 그 노드를 참조할 것 이다.
  // 그렇니 pointer 인스턴스가 null 값을 가지지 않는다면, 트리에 t 값을 가진 노드가 존재한다고 볼 수 있다.
  return pointer != null;
 }
}

2015년 1월 9일 금요일

[자료 구조] Tree

트리(Tree) 구조란 무었인가?

링크드 리스트, 스택, 큐는 모두 직선형 구조를 가지고 있다. 직선형 자료 구조는 1차원적 구성 위주고 이는 곧 계층적, 계급적 구조를 표현하는데 한계를 가지고 있다. 우리가 이번에 다룰 트리(Tree) 자료 구조는 노드(Node)들과 가지(Branch)들로 이루어진 비선형 자료 구조이다. 트리(Tree)의 최상위에는 뿌리(Root), 즉 루트 노드가 위치하며 그 아래로 자식(Child) 노드들이 가지(Branch)들을 통해 연결된다. 맨 아래의 노드들은 보통 잎(Leaf), 리프 노드라 불린다. 루트(Root) 노드를 제외한 모든 노드(Node)들은 부모(Parent) 노드를 가지며, 잎(Leaf) 노드를 제외한 모든 노드들은 자식(Child) 노드를 가진다. 그리고 모든 노드들은 가지(Branch)들로 연결되있다. 아래 그림은 트리 구조와 각각 파트의 이름, 주요 용어들을 정리해놓은 그림이다.


트리(Tree) 컨셉과 주요 용어들
트리(Tree) 컨셉과 주요 용어들

위의 그림에 나와있듯, 최상위에 위치한 노드는 뿌리(Root) 노드라 불리며, 가장 아래에 위치한 노드는 잎(Leaf)노드라 불린다. 그리고 트리(Tree)는 서브 트리(Sub Tree) 라 불리는 작은 트리들로 구성되있고, 서브 트리(Sub Tree) 들 또한 작은 트리들로 구성되있다. 위 그림 예제 같은 경우에는 왼쪽 서브 트리가 B 노드 부터 시작하고, 오른쪽 서브 트리는 C 노드 부터 시작한다. 그리고 B노드나 C 노드 둘다 아래로 서브 트리를 두지 않는다, 왜냐하면 D, E, F, G 노드들 모두 자식 노드가 없으니까~.

트리에서 조상(Ancestor) 관계와 후손(descendant) 관계란?

E 라는 노드가 T 노드의 조상(Ancestor)일 때, E 노드는 T 노드의 부모(Parent) 노드 이거나, T 노드의 부모(Parent) 노드의 조상(Ancestor)라 할 수 있다.
T 노드가 E 노드의 후손(Descendant)라 할 때, T 노드는 E 노드의 자식(Child) 노드 이거나, E 노드의 자식(Child) 노드의 후손(Descendant)라 할 수 있다.

노드(Node)의 깊이(Depth)란? 그리고 어떻게 계산되는가?

깊이란 루트(Root)노드에서 본인 위치까지에 있는 경로의 길이 이다. 노드 E 가 뿌리(Root) 노드라 할 때, 노드 E의 깊이(Depth)는 0이다. 루트(Root) 노드에서 한가지(Branch)씩 건너갈 때 마다 깊이는 +1 이 된다.

위의 그림을 예제로 들때
깊이 0 을 가진 노드는 : A
깊이 1 을 가진 노드는 : B, C
깊이 2 을 가진 노드는 : D, E, F, G
가 된다.

전체의 깊이(Depth Of Tree)란 최 하위에 위치한 잎(Leaf) 노드의 깊이(Depth)를 말한다. 위 그림의 경우에 Depth Of Tree는 2 가 된다.

트리 순회(Traversal)란? 그 종류, "Preorder"(전위), "Postorder"(후위), "Inorder"(중위) 순회는 어떻게 실행되는가?

  • 전위 순회(Preorder traversal)

    • 전위 순회(Preorder traversal)은 부모(Parent) 노드에서 자식(Child)노드로 진행된다
    1. 첫번째로 루트 노드를 방문한 후, 루트노드의 왼쪽 자식 노드로 이어간다
    2. 왼쪽 서브 트리를 전위 순회방식으로 순회한다.
    3. 그 후 오른쪽 서브 트리를 전위 순회방식으로 순회한다.
    • 위의 그림 예제에 나와있는 트리를 전위 순회 방식으로 순회하면
    • ABDECFG 와 같다.

  • 후위 순회(Postorder traversal)

    • 후위 순회(Postorder traversal)은 자식(Child) 노드에서 부모(Parent)노드로 진행된다
    1. 가장 왼쪽 아래에 위치한 자식노드를 방문한다, 그리고 그 자식 노드의 형제 노드를 방문한 후, 부모 노드로 진행한다.
    2. 왼쪽 서브 트리의 최 상위 노드에 도달할 때 까지 후위 순회를 진행한다
    3. 그 후, 오른쪽 서브 트리에서 후위순회를 진행한다.
    4. 마지막으로 루트 노드를 방문함으로써 후위순회를 마친다.
    • 위의 그림 예제에 나와있는 트리를 후위 순회 방식으로 순회하면
    • DEBFGCA 와 같다

  • 중위 순회(Inorder traversal)

    • 중위 순회(Inorder traversal)은 가장 아래 왼쪽 자식 노드에서 시작해 부모 노드를 거친 후에 오른쪽 자식 노드(시작 노드의 형제 노드)로 이어간다
    1. 가장 왼쪽 잎(leaf) 노드를 방문한다, 그리고 그 부모 노드를 방문 후, 아래로 형제 노드를 방문한다
    2. 이러한 방식으로 루트 노드까지 중위 순회를 이어간다.
    3. 그리고 오른쪽 서브 트리를 중위 순회로 순회한다
    • 위의 그림 예제에 나와있는 트리를 후위 순회 방식으로 순회하면
    • DBEAFCG 와 같다

2015년 1월 7일 수요일

[자료 구조] 큐(Queue)

자바(Java)로 구현한 큐(Queue) 예제


큐(Queue) 컨셉
큐(Queue) 컨셉

큐(Queue)란 무었인가?

큐는 직선형 자료 구조로써, 같은 타입의 데이터를 "하나 다음 하나" 라는 컨셉으로 순차적으로 저장하는 자료형이다. 스택(Stack)과는 달리, 큐(Queue)는 구조의 양 끝 모두에 접근이 가능하다. 맥도날드나 카페에서 줄을 서서 기다리는 걸 머리속에 그려보자. 줄은 새로운 사람이 끝에 섬으로써 길어지고, 가장 앞에선 사람이 주문을 함으로써 짧아진다. 이게 바로 큐(Queue)이다. 이렇한 이유로, 큐(Queue)는 보통 "FIFO(First In First Out) Structure"(먼져 들어간게 먼져 나오는 구조)라 영어권에서 표현된다.

큐(Queue) 실제로 어디에 쓰일까?

  • Operating System
    • 시스템 스케줄링, 인풋 버퍼(Input Buffer), 그리고 프린터 작업 관리 등

큐(Queue)는 어떻게 구현될까?

큐(Queue)는 스택(Stack)처럼 추상 자료형(Abstract Data Type)이므로, 다양한 방법으로 구현될 수 있다. 자바(Java)로 구현할 때 가장 많이 쓰이는 두가지 방법은 배열(Array)와 링크드 리스트(Linked List)를 이용하는 것이다. 큐(Queue)는 몇가지 필수적인 메소드들을 가지고 있는데 그것들은 아래와 같다
  • Enqueue(삽입)
    • 큐(Queue)의 끝에 새로운 자료를 삽입한다
    • 이 작업은 O(1)의 복잡도를 가진다
  • Dequeue(제거)
    • 큐(Queue)의 가장 첫 위치에 존재하는 자료를 반환하고 제거한다.
    • 이 작업은 O(1)의 복잡도를 가진다
  • Peek
    • 큐(Queue)의 처음에 존재하는 자료를 반환한다
    • Dequeue 메소드와는 달리, 처음에 존재하는 자료를 제거하지는 않는다.
  • isEmpty
    • 큐(Queue) 가 Empty 상태인지 확인한다.
  • clear
    • 큐(Queue) 내부의 모든 자료들을 삭제한다

아래는 자바(Java) 배열(Array)로 구현한 큐(Queue)의 예제이다


public class QueueWithArray {
 private Object[] queue;
 int first, last, size;
  public QueueWithArray(int size) {
  queue = new Object[size];// 주어진 인터져 size 값으로 size의 크기를 가진 오브젝트 어레이를 생성한다.
  first = last = -1;
  // 우선 아무것도 없는 배열에서, 우리의 마지막, 첫번째 데이터를 가리키는 first, last 인스턴스는 -1인덱스를 가리킨다.       
  this.size = size;// clear 메소드를 위해 사이즈 값을 저장해두자.
 }

 public boolean isEmpty() {
  return first == -1;
  // 만약 first 포인터 인스턴스가 -1 의 인덱스를 가리킨다면 그건 큐(Queue)가 empty 상태라는 뜻이다
 }

 public void clear() {
  queue = new Object[size]; // 새로운 배열(Array)를 생성하면서 원래 큐를 지워버리자
  first = last = -1;// 포인터 인스턴스를 리셋해준다.
 }

 public boolean isFull() {
   // 큐(Queue)가 꽉 찾는지를 확인한다.
   if ((first == 0 && last == size - 1) || first == last + 1) {
   // first 포인터가 인덱스 0, last 포인터가 배열의 마지막 인덱스(size - 1)를 가리키거나
   // first 포인터가 가리키는 인덱스가 last 포인터가 가리키는 인덱스보다 1이 크다면
   // 이는 큐(Queue)에 쓰는 배열이 꽉 찾음을 의미한다.
   return true;
  } else {
   return false;
  }

 }

 public void enQueue(Object e) {
  if (isFull()) {
   throw new FullQueueException();// 큐가 꽉 찾다면 Exception을 던져주자
  } else {
   //아니라면 삽입을 시작한다.
   if (first == -1) {// 만약 first 인스턴스가 -1값을 가지고 있다면, 이는 큐가 empty 상태인걸 의미한다.
    first = last = 0;// 그렇니 first 와 last 값을 0으로 바꿔주자
   } else {
    last = (last + 1) % size;
    // 이 메소드에서 새로운 object e 는 어레이의 가장 끝 인덱스의 위치로 삽입된다.
    // (last + 1) % size 는 배열(Array)의 중간에 last 인덱스가 위치할 경우를 생각한다.
   }
   queue[last] = e;
  }
 }

 public Object dequeue() {
  if (isEmpty()) {
   // 큐(Queue)가 Empty 인지 확인한다
   throw new EmptyQueueException();
  } else {
   Object toReturn = queue[first];
   if (first == last) {
    // first 와 last 가 같은 인덱스를 가리킨다면
    // 이는 큐(Queue)에 데이터가 1개밖에 없음을 의미한다.
    // 그렇니 그냥 포인터를 리셋해주자
    first = last = -1;
   } else {
    first = (first + 1) % size;
    // 만약 first 포인터가 배열(Array)의 마지막 인덱스를 가리키고 있다면
     // first + 1 은 ArrayOutOfBound Exception 을 낳을 것이다
     // first = (first + 1) % size; 은 그럴경우에는 0 이란 수가 계산되어
     // 옭바른 인덱스를 계산 할 수 있다.
   }
   return toReturn;
  }
 }

 public Object peek() {
  if (isEmpty()) {
   throw new EmptyQueueException();
  } else {
   return queue[first];
  }
 }
}



아래는 자바(Java) Linked List 로 구현한 큐(Queue)의 예제이다


import java.util.LinkedList;
public class QueueWithLinkedList {
 private LinkedList queue;

 public QueueWithLinkedList() {
  queue = new LinkedList();
 }

 public boolean isEmpty() {
  return queue.isEmpty();
 }

 public void enQueue(Object e) {
  queue.addLast(e);
 }

 public Object deQueue() {
  return queue.removeFirst();
 }

 public Object peek() {
  return queue.getFirst();
 }
}

[자료 구조] 스택 (Stack)

자바(Java)로 구현한 스택 예제


스택(Stack) 컨셉
스택(Stack) 컨셉

스택(Stack)이란 무었인가?

스택은 같은 타입의 자료를 "하나 다음 하나"라는 컨셉으로 순차적으로 저장하는 직선형 자료 구조이다. 우리가 스택에서 자료를 추출하고 삽입할 때 우리는 순렬의 끝에만 접근이 가능하다. 위 그림을 잠시 보자. 새로운 데이터는 스택의 최상위에 위치하게되고, 데이터 추출시, 우리는 오직 가장 최근에 삽입된 데이터만(최상위) 접근이 가능하다. 이 이유때문에 스택은 보통 "LIFO(Last In First Out)" 구조 라는, 가장 최근에 들어간게 가장 먼져 나온다는 뜻을 가진 어문으로 표현되기도 한다.

스택(Stack)은 실제로 어디에 사용되는가?

  • Operating Systems 
    • 프로그램에서 불러지는 함수(Method)들을 모두 Stack 이라는 자료형에 저장한다.
  • Compilers(컴파일러)
    • 컴파일러에서 수학기호들을 기계어(Machine Code)로 변환시, 괄호들을 매칭하거나 할 때.
  • JVM(Java Virtual Machine)자바 가상 머신
    • 자바 프로그램이 실행될 때 사용되는 JVM 에서도 스택은 사용된다. 각각의 스레드는 1개의 스택을 가지고 모든 메소드들을 트랙킹한다. 새로운 메소드들이 호출 될 때 마다, 새로운 프레임이 스택에 삽입되고, 메소드가 끝날 때 마다 스택에서 제거된다

스택(Stack)은 어떻게 구현될수 있을까?

앞에서 다룬 링크드 리스트와 달리 스택(Stack)은 추상 자료형(Abstract Data Type)이다. 추상 자료형이란 수학적 모델을 가진 자료형이고, 이는 곧 매우 다양한 방법으로 구현될 수 있음을 의미한다. 가장 자주 쓰이는 2가지 구현방법들은, ArrayList(어레이리스트)와 LinkedList(링크드 리스트)이다. 스택은 몇가지 필수적인 메소드들을 가지고 있는데 이는 아래와 같다
  • pop(추출)
    • 가장 최 상위에 위치한 자료를 추출한 후에 스택에서 제거한다
    • 이 작업은 O(1)의 복잡도를 가진다
  • push(삽입)
    • 스택의 최 상위에 새로운 자료를 삽입한다
    • 이 작업은 O(1)의 복잡도를 가진다
  • isEmpty
    • 스택이 empty 상태인지 확인한다
  • clear
    • 스택에 존재하는 모든 자료들을 삭제한다
  • peek
    • 가장 최 상위에 위치한 자료를 추출한다
    • pop 메소드와는 달리 스택에서 제거하지는 않는다.
    • 이 작업은 O(1)의 복잡도를 가진다

스택 Push 메소드
스택 Push 메소드

스택 Pop 메소드
스택 Pop 메소드

아래는 자바의 어레이리스트 api(java.util.ArrayList)로 구현한 스택(Stack) 자료형 이다


public class StackWithArrayList {
import java.util.*;//import arrayList

public class StackWithArrayList {
 private ArrayList stack;

 /**
  * 스택 인스턴스를 생성하는 컨스트럭터(Constructor)
  */
 public StackWithArrayList() {
  stack = new ArrayList();
 }

 /**
  * 스택을 최소 사이즈 s 로 생성한다
  * 
  * @param s 구현할 스택의 최소 사이즈
  */
 public StackWithArrayList(int s) {
  stack = new ArrayList();
  stack.ensureCapacity(s);
 }

 /**
  * 스택을 비운다
  */
 public void clear() {
  stack.clear();
 }

 /**
  * 스택이 Empty 상태인지 확인한다
  * 
  * @return 스택이 Empty 상태이면 true값을, 아니면 false 값을 반환한다.
  */
 public boolean isEmpty() {
  return stack.isEmpty();// 또는 "stack.size() == 0"를 이용할수도 있다
 }

 /**
  * 새로운 요소를 삽입한다
  * 
  * @param e 삽입될 새로운 요소
  */
 public void push(Object e) {
  stack.add(e);// ArrayList의 가장 마지막 index 에 새로운 요소를 삽입한다
 }

 /**
  * 스택에서 가장 최 상위에 위치한 데이터를 추출한 후 제거한다.
  * 
  * @return 스택에서 가장 최 상위에 위치한 데이터
  */
 public Object pop() {
  if (isEmpty()) {// 우선 스택이 empty 인걸 확인한 하고
   throw new EmptyStackException();
   // 그렇다면 Exception 을 던진다
  } else {
   return stack.remove(stack.size() - 1);
   // ArrayList.remove 메소드는 어레이에서 주어진 인덱스의 데이터를 제거후, 리턴한다 
  }
 }

 /**
  * 스택에서 가장 최상위에 위치한 데이터를 리턴한다, pop 메소드와는 달리 제거하지 않는다.
  * 
  * @return 스택에서 가장 최 상위에 위치한 데이터
  */
 public Object peek() {
  if (isEmpty()) {
   throw new EmptyStackException();

  } else {
   return stack.get(stack.size() - 1);
   // ArrayList.get 메소드는 주어진 인덱스에 저장된 값을 반환한다.
  }
 }
}


아래는 자바의 링크드리스트 api(java.util.LinkedList)로 구현한 스택(Stack) 자료형 이다

import java.util.EmptyStackException;
import java.util.LinkedList;

public class StackWithLinkedList {
 private LinkedList stack;

 public StackWithLinkedList() {
  this.stack = new LinkedList();
 }

 /**
  * 스택을 비운다
  */
 public void clear() {
  stack.clear();
 }

 /**
  * 스택이 Empty 상태인지 확인한다
  * 
  * @return 스택이 Empty 상태이면 True 값을, 아니면 false 값을 리턴한다
  */
 public boolean isEmpty() {
  return stack.isEmpty();// 또는 "stack.size() == 0" 구문을 이용할 수도 있다
 }

 /**
  * 스택에 새로운 데이터를 삽입한다.
  * 
  * @param e 삽입할 데이터
  */
 public void push(Object e) {
  stack.addLast(e);// 어레이리스트의 가장 마지막 인덱스에 추가한다.
 }

 /**
  * 스택에서 가장 최 상위에 위치한 데이터를 추출한 후 제거한다.
  * 
  * @return 스택에서 가장 최 상위에 위치한 데이터
  */
 public Object pop() {
  if (isEmpty()) {// 우선 스택이 empty 상태인지 확인한후
   throw new EmptyStackException();
   // empty 상태라면 Exception 을 던진다.
  } else {
   return stack.removeLast();
   // ArrayList.removeLast 메소드는 가장 마지막 인덱스에 위치한 자료를 어레이에서 리턴하고 제거한다
  }
 }

 /**
  * return 스택에서 가장 최상위에 위치한 데이터를 리턴한다, pop 메소드와는 달리 제거하지 않는다.
  * 
  * @return 스택에서 가장 최 상위에 위치한 데이터
  */
 public Object peek() {
  if (isEmpty()) {// 우선 스택이 empty 상태인지 확인한후
   throw new EmptyStackException();
   // empty 상태라면 Exception 을 던진다.
  } else {
   return stack.getLast();
   // ArrayList.getLast 메소드는 가장 마지막 인덱스에 위치한 데이터를 리턴한다.
  }
 }
}

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;
  }
 }