본문 바로가기
Java/자료구조

[자료구조] 선형구조(Linear Structure)

by WaterPunch 2022. 1. 21.
  • 선형구조(Linear Structure)란
    • 자료를 구성하는 원소들을 순차적으로 나열시킨 형태를 의미
    • 어떤 연산들을 수행할 수 있느냐에 따라 세부적으로 나뉠 수 있음
    • 선형구조는 위와 같이 1부터 4까지 순차적으로 원소를 나열시키는 형태
    • 선형구조는 대표적으로 리스트(List)와 큐(Queue), 덱(Deque)이 있음

선형구조


  •  배열(Array)
    • 같은 자료형을 갖는 여러 데이터를 하나의 변수 이름으로 모아놓은 데이터의 집합체
    • 인덱스(index)를 가지고 있으며, 순차적으로 데이터가 삽입 삭제될 수 있는 형태의 자료구조

장점 인덱스를 사용하기 때문에 검색이 빠르다
단점 중간에 삽입 삭제가 어렵다
(삽입/삭제 연산이 빈번하게 일어나는 연산에는 부적절)

 


 

  • 연결 리스트(Linked List)
    • 노드라는 저장구조를 이용해서 선형 리스트를 표현하는 방법
    • 리스트의 데이터를 노드(node) 또는 요소(element)라고 함
    • 자료를 저장하는 노드에는 자료와 다음 노드를 가리키는 링크(포인터)가 있음
    • // Java에서의 Node<E> 
      private static class Node<E> { 
      	E item; // 데이터 
          Node<E> next; // 다음 노드를 가리키는 포인터 
          Node<E> prev; // 이전 노드를 가리키는 포인터 
          
          Node(Node<E> prev, E element, Node<E> next) { 
          	this.item = element; 
              this.next = next; 
              this.prev = prev; 
      	} 
      }
    • 논리적순서와 물리적순서가 같지 않다
    • 링크 필드의 조정을 통해 비교적 간단하게 삽입/삭제 연산을 할 수 있다
    • 연결을 위한 포인터 부분이 필요하기 때문에 순차리스트(배열)에 비해 기억공간 이용 효율이 좋지는 않다
    장점 중간 삽입 삭제가 빠르고 용이하다
    단점 검색 속도, 접근 속도가 느리다
    (순차접근을 해야하기 때문에 검색시 배열보다는 효율이 떨어지는 편)

 

  • 스택(Stack)
    • 한쪽 끝에서만 데이터의 삽입과 삭제가 수행되는 선형 리스트
    • 가장 나중에 입력 된 자료가 가장 먼저 출력되는 자료구조(LIFO : Last In First Out)
    • push : 데이터를 삽입하는 연산, top을 위로 한 칸 올리고, top이 가리키는 위치에 데이터 저장
    • pop : 데이터를 삭제, 출력하는 연산, top이 가리키는 데이터를 반환하고, top을 아래로 한칸 내린다
    • peek : 스택의 top에 있는 item을 반환한다. pop과 달리 stack에서 객체를 꺼내지 않는다.
    • top에서만 데이터의 삽입과 삭제가 수행된다

Stack

 

 


 

  • 큐(Queue)
    • 한쪽 끝에서는 데이터의 삽입만 수행되고, 다른 한쪽 끝에서는 삭제만 수행되는 선형 리스트
    • 가장 먼저 들어간 데이터가 가장 먼저 나오는 선입선출 (FIFO : First In First Out) 형식의 자료구조
    • 가장 앞부분(삭제지점)을 front / head라고 하며, 가장 뒷부분(삽입지점)을 rear / tail이라고 함
    • 순서를 기다리는 대기행렬처리나, 운영체제의 작업 스케쥴링에 사용됨

Queue

 

 


 

  • 덱(Deque)
    • 큐(Queue)와 스택(Stack)을 합친 형태로 생각할 수 있음
    • 삽입/삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료구조
    • scroll : 입력 제한 덱, 입력이 한쪽에서만 발생하도록 제한
    • self : 출력 제한 덱, 출력이 한쪽에서만 일어나도록 제한

Deque

반응형

'Java > 자료구조' 카테고리의 다른 글

[자료구조-Java] Class 클래스?  (0) 2022.01.18
[자료구조-Java] 배열(Array)?  (0) 2022.01.16

댓글