목록자료구조 (13)
Binaryseop
1. 스택(Stack) 스택의 사전적 의미는 '쌓다'입니다. 쌓여있는 접시, 책상 위에 쌓아 둔 책과 같이 차곡차곡 쌓아 올린 형태의 구조를 스택(Stack)이라 부릅니다. 이와 같이 일상에서 사용하는 스택의 개념을 추상화하여 자료구조로 만든 것이 스택 자료구조입니다. 2. 스택의 특징 1) 데이터의 삽입과 삭제는 top이라고 부르는 한쪽 끝에서만 이루어지도록 제한하여 만든 자료구조입니다. · 삽입 연산은 top의 위치를 하나 증가시킨 뒤 top이 가리키는 위치에 데이터를 삽입합니다. · 삭제 연산은 top이 가리키고 있는 데이터를 스택에서 삭제하고 top의 위치를 하나 감소시킵니다. 2) 스택은 시간순서에 따라 데이터가 쌓이고, 삭제할 때는 가장 마지막에 삽입된 데이터가 가장 먼저 삭제되므로 후입선출(..
1. 이중 연결 리스트 단순 연결 리스트에서 이전 노드에 접근하기가 어렵다는 점을 개선하여 원형 연결 리스트를 구성했지만, 원형 연결 리스트에서도 현재 노드의 바로 이전 노드에 접근하려면 전체 리스트를 한바퀴 순회해야 하는 문제가 있습니다. 이러한 문제는 리스트를 구성하는 노드의 링크 방향이 한 방향으로만 되어있기 때문에 발생합니다. 따라서 이러한 문제를 개선하기 위해 양쪽 방향으로 순회할 수 있도록 연결한 리스트를 이중 연결 리스트(Doubly Linked List)라고 합니다. 2. 이중 연결 리스트 구현 이중 연결 리스트는 양쪽 방향으로 순회할 수 있어야 합니다. 따라서 왼쪽 노드를 연결하는 링크 필드와 오른쪽 노드를 연결하는 링크 필드 그리고 데이터를 저장하는 데이터 필드로 구성된 노드를 연결하여..
연결 리스트 선형 리스트는 논리적인 순서와 물리적인 순서가 같기 때문에 원소의 위치를 찾아 접근하기 쉽다는 장점이 있지만, 삽입이나 삭제 연산 후에 논리적인 순서와 물리적인 순서를 유지하기 위해 원소들을 이동시키는 추가적인 작업과 시간이 필요합니다. 따라서 원소의 개수가 많고 삽입 · 삭제 연산이 많이 발생하는 경우 원소들의 이동 작업으로 인한 오버헤드가 증가하여 성능상에 문제를 일으킬 수 있습니다. 또한 배열을 이용하여 구현하기 때문에 크기가 제한되고 메모리 사용의 비효율성 문제를 갖고 있습니다. 이러한 선형 리스트에서 추가적인 오버헤드 문제와 저장 공간에 대한 문제를 개선한 자료 표현 방식이 연결 리스트(Linked List)입니다. 연결 리스트는 연속한 메모리 물리주소에 원소의 순서를 표현하는 것이..
선형 리스트 데이터를 구조화시키는 가장 기본적인 방법은 나열하는 것입니다. 예를 들어, 좋아하는 음식을 나열하거나 오늘의 할 일을 나열하는 것 등 이렇게 나열한 목록을 리스트(List)라고 합니다. 이와 같이 리스트에서 나열한 원소들 간에 순서를 가지고 있는 리스트를 선형 리스트(Linear List)라고 합니다. 선형리스트 특징 선형 리스트는 배열을 이용하여 구현하기 때문에 원소들의 논리적인 순서와 메모리에 저장되는 물리적인 순서가 같다는 특징이 있습니다. 선형 리스트 구현 선형 리스트는 배열을 이용하여 구현할 수 있습니다. · 1차원 배열의 순차 표현 public class MainForOneDimensionalArray { public static void main(String[] args) { i..