자료구조-알고리즘/선형 자료구조

선형 자료구조: 자료구조 소개

vita12321 2023. 8. 18. 15:33
728x90
반응형

이 글에서는 선형 자료구조의 개념과 원리, 주요 선형 자료구조(배열, 연결 리스트, 스택, 큐)를 자세하게 살펴보고, 이에 관련된 예제 코드를 자바를 이용하여 체계적으로 소개하겠습니다.

1. 선형 자료구조의 개념 및 원리 이해

 

1) 선형 자료구조

선형 자료구조는 데이터 항목들이 선(line)처럼 일렬로 배열되어 있는 구조를 말합니다. 각 항목은 바로 앞 또는 바로 뒤의 항목과만 관련이 있으며, 이를 사용하여 데이터를 관리하고 처리할 수 있습니다. 선형 자료구조는 프로그래밍에서 데이터를 표현하고 조작하는데 사용되며 주요한 구현 방법으로 배열, 연결 리스트, 스택, 큐 등이 있습니다.

 

2) 주요 선형 자료구조

 

주요 선형 자료구조로는 배열(Array), 연결 리스트(Linked List), 스택(Stack), 큐(Queue) 등이 있습니다. 이들 각각의 특징과 장단점을 이해하고 적절한 상황에 활용하면 프로그램의 효율성을 높일 수 있습니다.

2. 배열(Array)

 

배열은 고정된 크기의 연속된 메모리 공간으로 데이터를 저장합니다.

인덱스를 이용하여 빠르게 데이터에 접근할 수 있지만, 임의의 위치에 데이터를 삽입하거나 제거하는 데에는 높은 비용이 듭니다.

배열의 장점 중 하나는 메모리 공간의 효율성입니다. 각 요소는 바로 다음 요소와 인접해 있어 메모리 공간을 최소화할 수 있습니다.

3. 연결 리스트(Linked List)

 

연결 리스트는 노드(Node)들이 포인터(Pointer)를 사용하여 연결되어 있는 구조입니다.

연속된 메모리 공간이 아니기 때문에, 크기 변경과 임의 위치에 대한 삽입과 제거 작업이 효율적입니다.

그러나 인덱스를 이용한 조회 작업이 느리며 차지하는 메모리 공간이 상대적으로 큽니다. 연결 리스트는 단일 연결 리스트(Singly Linked List)와 이중 연결 리스트(Doubly Linked List) 등의 형태로 구현됩니다.

4. 스택(Stack)

 

스택은 맨 위에 있는(top) 데이터 항목을 기준으로 데이터를 추가(push)하거나 제거(pop)하는 구조입니다.

후입선출(LIFO; Last In First Out) 원칙을 따르며, 이를 이용하여 숫자 계산, 표현식 변환, 주소 점프 등에 활용할 수 있습니다. 스택은 배열이나 연결 리스트를 사용하여 구현할 수 있으며, 두 가지 방식 모두 장단점이 있습니다.

5. 큐(Queue)

 

큐는 맨 앞에서(rear) 데이터를 제거(dequeue)하고 맨 뒤에(front) 데이터를 추가(enqueue)하는 구조입니다.

선입선출(FIFO; First In First Out) 원칙을 따르며, 스케줄링, 버퍼링, 프린터 대기열 등에 활용할 수 있습니다. 큐 역시 배열이나 연결 리스트를 사용하여 구현할 수 있으며, 이 또한 장단점이 존재합니다.

6. 자바를 이용한 선형 자료구조 예제 코드

 

선형 자료구조별로 예제 코드와 설명을 살펴보겠습니다. 이 글에서는 간단한 배열, 연결 리스트, 스택, 큐의 코드 예제를 제공합니다. 자세한 설명과 실습을 원하신다면, 각 자료구조에 대한 별도의 글이나 강의를 참조해 주세요.

 

 

  • 배열 예제
int[] intArray = new int[5];

intArray[0] = 1;

intArray[1] = 2;

 

  • 연결 리스트 예제
LinkedList<String> linkedList = new LinkedList<String>();

linkedList.add("Apple");

linkedList.add("Banana");

 

  • 스택 예제
Stack<Integer> stack = new Stack<Integer>();

stack.push(1);

stack.push(2);

int top = stack.pop(); // top에는 2가 저장됩니다.
  • 큐 예제
Queue<String> queue = new LinkedList<String>();

queue.add("Apple");

queue.add("Banana");

String first = queue.poll(); // first에는 "Apple"이 저장됩니다.

7. 결론

 

이 글에서는 선형 자료구조의 개념과 원리, 그리고 주요 선형 자료구조별로 자바를 이용하여 간단한 예제를 제공하였습니다. 각 자료구조의 특징과 장단점을 이해하고 적절한 상황에 활용하면 프로그램의 효율성과 가독성을 높일 수 있습니다. 선형 자료구조를 기반으로 다양한 알고리즘을 구현하고 최적화하는 데 도움이 될 것입니다.

728x90
반응형