스택의 정의와 연산 스택은 선입후출(FILO) 또는 후입선출(LIFO)의 특징을 가지는 자료구조로 나중에 들어온 데이터가 먼저 나가는 특징이 존재하는 자료구조이다. 이를 다른 말로 하면 한 곳(Tail)에서만 삽입과 삭제 연산이 일어나는 자료구조이다. 일반적으로 들어온 인풋의 역순으로 연산이 진행되어야 하는 경우 스택을 사용할 수 있다. 스택의 연산은 일반적으로 다음과 같이 나열할 수 있다. 데이터의 추가 데이터의 제거 데이터의 조회 스택의 상태(비어있는지) 스택의 구현 방법 스택은 배열과 리스트로 구현할 수 있다. 배열과 리스트의 장 단점은 각각 다른데 배열의 초기 길이를 변경하지 못한다는 크리티컬한 단점으로 인해 일반적으로 연결 리스트를 이용하여 구현하게 된다. 이번에도 Node Pool을 이용한다...

Single Linked List의 구현 - 계속 이전까지 연결 리스트의 head 또는 tail에 노드를 삽입하는 것을 구현하였다. 이번에는 임의의 위치를 입력받아 그곳에 노드를 삽입하는 연산과 데이터를 입력받아 그 데이터와 동일한 값을 가진 노드를 찾아 삭제하는 연산을 수행할 것이다. 임의의 위치에 노드를 삽입하는 연산 연결 리스트에서 임의의 위치에 노드를 삽입하기 위해서는 먼저 그 위치가 어디인지부터 파악하는 것이 먼저 수행되어야 할 것이다. 이는 연결 리스트의 특성을 생각해 보면 리스트를 순회하며 그 위치를 찾아야 한다. 그렇다면 그 위치에 삽입하면 될 것이다. 여기서 생각을 깊게 하지 못하면 실수가 발생한다. 임의의 두 노드 사이에 노드를 추가하려면 어떤 과정이 수반되어야 하는지 생각해야 한다. ..

단방향 연결 리스트의 구현 이번에는 단방향 연결 리스트를 Java를 사용하여 구현할 것이다. 문제는 다음과 같다. 각 명령을 문제없이 수행하는 LinkedList클래스를 작성하라 LinkedList 클래스는 다음과 같은 연산을 가진다. 초기화 리스트의 처음에 데이터 삽입 리스트의 마지막에 데이터 삽입 리스트의 임의의 위치에 데이터 삽입 data와 동일한 값을 가진 데이터를 리스트에서 삭제 이때 어떠한 Java 라이브러리도 사용하면 안된다. 데이터는 int형 정수 데이터로 제공되며 메서드 전체의 호출 수는 1만번을 초과하지 않는다고 가정한다. Node의 정의 이전 연결 리스트의 정의와 구조에서 보았듯이 연결 리스트는 Node, head로 구성되며 Node는 데이터를 저장하는 곳과 자신의 다음 Node가 존..

LinkedList의 개념과 종류 LinkedList의 개념을 알아보기 전에 배열에 대해서 먼저 알아보도록 하자. 배열(Array)은 동일한 자료형을 연속적인 메모리 공간에 저장하는 자료구조이다. 연속적인 메모리 공간에 저장되기 때문에 무작위 접근(Random Access)가 가능하다. 대신 초기에 설정해놓은 크기를 조절하기가 불가능하며 데이터의 삽입 삭제 연산 속도가 느리다. 연결 리스트는 배열의 단점을 해결하기 위해 나온 개념으로 연속적인 메모리 공간에 저장하는 것이 아닌 여러 메모리 공간에 저장한다. 그렇다면 이를 어떻게 리스트처럼 연결할까가 문제가 된다. 연결 리스트는 현재 데이터의 다음 데이터가 메모리의 어느 위치에 존재하는지에 대한 데이터 next 를 가지고 있다. 따라서 데이터를 접근할 때 ..