기타 정보/자료구조: 17개의 글
Java 스택(Stack) 정리 1. 스택(Stack)의 개요 스택(Stack)은 사전적으로 '더미', '쌓아 올림' 이라는 의미를 가진다. '더미'란 '많은 물건이 한데 모여 쌓인 큰 덩어리'를 의미한다. 스택(Stack)은 데이터를 쌓아올리는 형태로 저장하여 추출할때는 맨 위에 있는 데이터를 먼저 꺼내는 형태이기 때문에 제일 마지막에 저장한 데이터를 제일 먼저 꺼내는 후입선출(LIFO - Last In First Out) 형태의 자료구조이다. 스택(Stack)은 가장 마지막의 데이터의 위치에 대해 삽입이나 삭제가 발생하므로, 이러한 구조에 사용될 때 간단하며, 더욱 효율적이고 쉽게 사용이 가능하다. 가장 최근에 입력된 데이터를 top 이라고 하며 스택은 top에서만 삽입, 삭제, 읽기 동작이 발생할 ..
Java 이중 연결 리스트 (doubly linked list) 정리 단순 연결 리스트의 노드는 다음 노드에 대한 참조만 가지고 있기 때문에 노드를 단방향으로 밖에 탐색하지 못한다.이중 연결 리스트(doubly linked list)의 노드는 다음 노드 뿐만 아니라 이전 노드의 참조까지 추가하여 양방향으로 탐색이 가능하도록 만들어 검색속도를 향상시킬 수 있는 방법을 제공한다. 단순 연결 리스트나 이중 말단 연결 리스트는 처음 노드에서 마지막 노드로의 방향밖에 탐색을 할 수 없으므로 검색하려는 데이터가 리스트의 뒷부분에 위치할 경우 전체 요소의 절반 이상을 순차 접근해야 하므로 검색에 필요한 평균적인 접근이 데이터수/2 가 된다. 이중 연결 리스트는 다음 노드의 참조와 이전 노드의 참조를 모두 가지고 있기..
Java 이중 말단 연결 리스트(double ended linked list) 정리 단순 연결 리스트는 첫번째 노드에 대해 삽입, 삭제 작업을 할 경우 빠른 처리능력을 보여주지만 마지막에 데이터를 삽입, 삭제 할 경우 처음부터 끝까지 순차 검색을 하여 마지막 노드를 찾아야 하기 때문에 저장된 데이터의 수가 많아 질수록 그 효율이 떨어진다. 반면에 이중 말단 연결 리스트(double ended linked list)는 헤더에 처음 노드의 참조와 함께 마지막 노드에 대한 참조도 같이 저장함으로써 마지막 노드에 대한 접근을 빠르게 처리할 수 있다는 장점을 가진다. 단순 연결 리스트는 리스트의 처음 노드에 데이터를 저장하고 처음 노드의 데이터를 꺼내는 작업에 좋은 효율을 가지므로 마지막에 저장한 데이터를 먼저 ..
Java 단순 연결 리스트(simple linked list) 정리 단순 연결 리스트(simple linked list, singly linked list)는 가장 단순한 연결 리스트의 형태로 각 노드들은 다음 노드를 가리키는 하나의 참조만을 갖는다. 다음 노드의 참조밖에 가지고 있지 않으므로 노드의 접근은 한 방향으로만 가능하다. 헤더는 처음 노드의 참조만 가지고 있으며 처음 노드는 두번째 노드, 두번째 노드는 세번째 노드를 가리키고 있으며 마지막 노드가 가리키는 참조값은 null이 된다.즉, 헤더가 가리키는 노드가 처음 노드며 참조값이 null인 노드가 마지막 노드가 되는 것이다. 1. 단순 연결 리스트의 기본 구조 public class MyLinkedList { private Node header..
Java 배열(array)과 리스트(list) 비교 리스트(list)란 데이터를 순차적으로 나열해 놓은 집합을 가리키는 자료구조의 추상적인 개념으로 비슷한 성질의 데이터를 순서를 고려하여 그룹화 시키고자 할 때 주로 사용하는 자료구조이다. 1. 배열을 이용한 구현 배열을 이용하여 리스트(list)를 구현할때의 가장 큰 장점은 쉽게 구현할 수 있다는 점이다. 배열은 내부 인덱스를 가지고 데이터에 접근할 수 있으므로 인덱스의 번호가 곧 데이터들의 순서를 의미하기 때문에 데이터 삽입시 순차적으로 인덱스 값을 증가시키면서 저장하면 되고 데이터를 검색 할 때에도 인덱스를 가지고 직접 접근하여 빠르게 찾을 수 있다.그리고 배열은 항상 인덱스 0부터 시작하기 때문에 첫 데이터를 쉽게 찾을 수 있으며 저장된 데이터의 ..
JAVA 배열을 이용한 자료의 관리 자료구조란 특정 큐칙을 적용한 자료의 집합을 의미한다. 자료구조 중에서 가장 기본이 되며 가장 단순한 구조인 배열은 동일한 형태(int, double, String, Object 등)의 자료들이 순서를 가지고 구성된 집합이다. 배열은 초기 생성시에 그 크기를 미리 지정해야 한다. 초기에 지정한 크기는 바꿀 수 없기 때문에 생성한 크기보다 많은 자료를 저장할 수 없어 효율적인 자료구조로 사용하는데 제약이 따르게 된다. 배열 내에 저장된 자료들은 그 위치 값(index)을 가지고 식별할 수 있으며 위치값은 자료의 절대적인 위치를 나타내므로 특정 데이터에 접근 할 경우 처음부터 탐색할 필요 없이 index를 가지고 직접 접근할 수 있다. 1. 배열의 선언, 생성 및 초기화 ..
자료구조의 개요, 특징, 분류 1. 자료, 정보, 자료구조 (1) 자료와 정보 자료(data)란 현실 세계로부터 수집한 사실이나 개념의 값 또는 이들의 집합을 의미한다. 흔히 가공되지 않은 형태의 데이터를 자료라고 하며 특정한 용도로 사용하기 위하여 자료를 처리/가공한 형태의 데이터를 정보(information)라고 한다. (2) 자료구조 자료구조(data structure)란 자료의 집합을 의미하며 각 원소들 사이의 관계가 논리적으로 정의된 일정한 규칙에 의하여 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 조직적, 체계적으로 구분하여 표현한 것을 말한다. (3) 자료구조의 선택 기준 작업의 효율성, 추상화, 재사용성을 증가시키기 위하여 상황에 따른 적절한 자료구조를 선택하여 사용해야..