분류 전체보기

0. 이중 연결 리스트 단일 연결리스트는 다음 노드를 가르키는 포인터 변수를 가지고 있었다면 이중 연결 리스트는 다음 노드 뿐만 아니라 이전 노드를 가르키는 포인터 변수까지 가지고 있는 노드로 이루어져있습니다. 즉 양방향으로 연결 된 리스트를 LinkedList 중에서도 Doubly LinkedList 라고 합니다.  이렇게 되면 단일 연결 노드보다 검색의 성능이 좋아집니다. 만약 10개의 노드가 있고, 9번째 노드를 검색하고 싶다면 단일 연결 노드에서는 head 노드부터 시작하여 거의 모든 노드를 거쳐서 가야합니다. 하지만 이중 연결 리스트는 10번, 9번 노드 단 두 번만에 검색할 수 있습니다.  1. Node 클래스 이전까지 사용되었던 Node 클래스와 달리 이전 노드를 가르키는 래퍼런스 변수 @p..

0. Singly LinkedList (단일 연결 리스트) 단일 연결 리스트는 LinkedList 의 한 종류입니다. 2024.04.19 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 7 - LinkedList 에서 설명한 LinkedList 와 동일한 자료구조입니다. 자세한 설명은 위 글을 보면 되고, 여기에 추가적인 메소드들을 더해 구현해보겠습니다.  1. Node public class Node { E data; Node next; // 다음 노드를 가르키는 래퍼런스 변수 Node(E data){ this.data = data; this.next = null; }}  2. Singly LinkedListimport Interface..

ArrayList ArrayList 는 List Interface 를 implements 하는 클래스입니다. 하지만 다른 List 자료구조들과 달리 배열에 기반을 두고 사용합니다.(다른 자료구조들은 주소를 통해 구현됩니다.) 또한 모든 자료구조는 '동적 할당' 을 전제로 합니다. 만약 ArrayList 를 사용하는데 리스트가 꽉찼다면 리스트의 길이를 늘려줘야 합니다. 이때 크기는 현재 크기의 2배씩 늘립니다.  ArrayList 구현 메소드 2024.04.26 - [자바[JAVA]/자바[JAVA] 자료구조 구현] - 자바[JAVA] 자료구조 구현 1 - List Interface에서 구현한 메소드들을 포함하여toArray() 와 clone() 을 추가해서 작성했습니다.해당 메소드들에 대한 설명은 코드 주..

0. Array and List 배열은 뭐고 리스트는 뭘까? 그리고 배열이 있는데 리스트를 써야하는 이유는 무엇일까?  0.1 Array 배열은 선형적인 자료구조 중의 하나로 데이터를 일렬로 늘여 놓은 형태의 자료구조입니다. 어떤 언어를 배우던 가장 기본적으로 배우게 되는 메모리 공간 형태이며, 자료형(Data Type)이 둘 이상의 값을 저장할 수 없습니다.(다만, Python 제외)  0.2 List 리스트도 배열과 마찬가지로 선형적인 자료구조 중의 하나입니다.  하지만 배열과 달리 길이가 가변적입니다. 이를 동적할당(Dynamic allocation)이라고 합니다. 또한 배열과 달리 메모리 공간상에 연속적으로 나열되어 할당되지 않고 주소(reference) 를 통해 데이터들이 연결되어있는 형태입니다..

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 0. Binary Search Tree Definition Node contains key which can make us identify from other nodes There is one Root node(unless empty BST, but if there is Dummy data in Root, we do not have to take care of it Root node may have "two" child node(s) Each child is the root node of its subtree Each subtree is itself a BST The key values in left subtree are all smaller t..

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 0. LinkedList LinkedList 는 Node 들로 구성되어있는 자료구조입니다. 노드는 저장요소들의 단위로 노드들을 포인터를 통해 서로 연결되어있습니다. 그래서 연결 리스트라 불립니다. 연결 리스트의 구조는 다음과 같습니다. 연결 리스트에는 head 라는 포인터를 통해 처음 요소를 가르킵니다. 또한 마지막 노드의 next 포인터는 null 값을 가르킴으로써 마지막 요소임을 나타냅니다. #include class Node{ public: Node(int data) : data{data}, next{NULL}{}; ~Node(){ std::cout data == x) return 1; else if((*l)->data < x){ *p = ..

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 0. Definition of Equivalance Relation Given a set A, a Relation on A is any subset of AxA There is a Relation R which is a Relation on A. for example, A = {1,2,3,4} , R = {(1,3), (3,4), (1,1), (2,2)} We can write 1R3 to mean (1,3) ∈ R An extreme example There is a Relation '

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 0. Queue and Stack 0.1 Queue Insert 와 Delete 만을 제공하는 자료구조 입니다. Queue 의 매우 주요한 특징으로는 FIFO(* First In First Out) 입니다. 앞서 봤던 Sorted Packed Array 같은 자료구조들과 달리 LinkedList 를 기반으로 합니다. LinkedList 의 특징을 통해 Queue 의 각 수행들은 매우 빠른 성능을 보입니다. 실제로 빨라야 하는 수행이기도 합니다. Queue 는 생각보다 많은 곳에 쓰이지는 않지만 알고있으면 유용한 순간들이 있습니다. 0.1.1 성능 Insert : O(1) Delete: O(1) 0.2 Stack Queue 와 마찬가지로 Inser..