Algorithm/자료구조 구현 (6) 썸네일형 리스트형 [자료구조] Queue 구현 컬렉션으로서의 큐 1. 큐는 인터페이스이고, 이를 구현하는 구현 클래스를 참조하게 업캐스팅하여 사용해야 한다. e.g. Queue queue = new LinkedList(); || Queue queue = ArrayDequeue(); 좌변과 우변의 타입이 일대일 대응(?)되는 형태의 컬렉션들은 모두 그 자체로 구현 클래스여서 그러하다. 하지만 큐는 그렇지 않으므로 LinkedList나 ArrayDequeu같은 구현 클래스를 통해서 사용할 수 있다. 2. 인덱스를 써야하는 상황에선 LinkedList를, 다른 경우은 ArrayDequeue가 더 성능이 좋다. 아래 자바 컬렉션 상속도를 보면 알겠지만, LinkedList는 Queue인터페이스와 Dequque 인터페이스를 모두 구현한다. 그리고 ArrayD.. [자료구조] Stack 구현 stack을 배열로 구현 삼단 논법처럼 생각하면 쉽다. 1. stack에서 데이터가 들어가고 나가는 입구는 top뿐이다. 2. 스택은 배열로 구현할 수 있다. 3. 배열에서 데이터에 접근할 때는 index를 이용한다. => 스택을 배열로 구현하면, top을 인덱스로 사용하며 이것이 데이터에 접근할 유일한 통로가 된다. 주의 사항 1) 데이터가 들어오지 않았을 때 top은 -1이다. 하나가 들어오면 그때 0으로 스택의 top을 표시해야 하므로 top은 -1로 초기화한다. 2) 배열로 스택을 구현하였을때, 길이가 정해져있다는 배열의 특성을 반영해야 한다. 따라서 push를 할 때는 배열이 가득 찼는지, pop이나 peek을 할 때는 배열이 empty는 아닌지 고려해야 한다. 이를 고려하지 않으면 top이 배.. [자료구조] Circular Doubly LinkedList 구현 싱글, 더블리 링크드 리스트와 기본적으로 동일하지만, tail까지 가는 방법이 다르다. 싱글, 더블리 링크드 리스트에서는 tail까지 이동하기 위해서 아래 코드를 사용했지만, Node cur = this.head; while (cur.next != null) { cur = cur.next; } 원형 링크드 리스트는 모든 노드가 연결되어있으므로 while(cur.next != null)을 그대로 사용하면, 무한 루프가 발생한다. 따라서 tail까지 이동하는 조건으로 cur.next != head를 사용해야 한다. 또는 head가 있다는 조건 하에, head.prev로 바로 tail에 접근할 수 있다. // tail 접근법 1 Node cur = this.head; while (cur.next != this.. [자료구조] Doubly LinkedList 구현 싱글리 링크드 리스트와 달리, Node에서 prev와 next를 모두 저장한다. 따라서 삽입과 삭제를 한 후에도 정상적인 구조를 유지하도록 prev와 next를 모두 수정해주야 한다. package DoublyLinkedList; class Node{ int data; Node next; Node prev; Node(int data, Node prev, Node next){ this.data = data; this.prev = prev; this.next = next; } } class DoublyLinkedList { Node head; boolean isEmpty() { if (head == null) { return true; } return false; } int getSize() { int si.. [자료구조] Singly LinkedList 구현 배열처럼 원하는 값에 한번에 접근할 수 없으니 모든 접근을 head를 통해서 해야한다. 또한, next 링크가 삽입과 삭제 이후에도 정상적으로 작동할 수 있게 next를 제대로 수정해줘야 한다. 특히 어디에서 (중간에서 or head에서 or tail에서) 삽입/삭제할 것인지에 따라서 다르게 처리해줘야 한다는 것을 주의해해야 한다. 삽입 삭제의 자세한 원리는 아래 그림 참고하면 된다. 코드 package SinglyLinkedList; public class Main { class Node{ int data; Node next; Node(int data, Node next){ this.data = data; this.next = next; } } class SinglyLinkedList { Node he.. [자료구조] LinkedList 란? 데이터를 집어넣는 방법 메모리 확보 후 연속된 공간에 채워넣기 vs 필요할 때마다 메모리를 할당받아 데이터를 저장 전자는 배열이고 후자는 연결리스트 즉, Linked List 라고 함 배열과 링크드 리스트의 차이 배열의 특징 : 미리 공간을 확보하지만, 확보되는 공간보다 적게 사용하면 메모리가 낭비될 수 있음 cf. 배열의 한 칸을 셀(cell), 또는 요소(element)라고 함 링크드 리스트 특징 : 낭비되는 데이터는 없지만, 연관 데이터끼리 '연결' 짓는게 필요함 node는 필요에 따라 동적으로 할당되고 자바에서는 자동으로 메모리를 정리해주므로 낭비되는 저장 공긴이 없음 하지만 data와 idx만 저장하는 배열과 달리 추가적으로 저장해야 될 것이 있으므로 그 자체의 저장 공간은 배열보다 큰 편 링크.. 이전 1 다음
