리스트란 자료의 삽입 삭제를 할 수 있는 순서 있는 자료의 집합으로 선형 리스트는 물리적으로 서로 이웃한 위치의 관계를 가진 리스트를 의미합니다.

선형리스트(Linear List)에 대해 알아 보도록 하겠습니다.

4-1. Stack

스택은 정보를 기록하거나 삭제할때 한쪽 끝에서만 이루어진다.

Stack구조는 프로그램의 서브루틴 호출(Subroutine Call)과 복귀(Return)를 처리할 때에 이용되는 기억 구조. 컵이나 우물의 개념을 갖으며, 나중에 들어온 자료를 먼저 제거하는 특징을 갖는다.LIFO(Lasr In First Out)

【예】Stack

컵, 우물 또는 지표의 화석을 파내려 가면서 조사하는 것

【참고】empty 상태

Top = 0인상태

4-2. Queue

우리의 일상생활과 가까운 형태로 먼저 입력된것이 먼저 제거된다.(FIFO →First In First Out)

【예】큐(Queue)

㉮ 수도의 파이프에 물이 지나가는 것

㉰ 차표를 사려고 줄을 서서 기다리는 것

㉱ 열차가 역을 지나가는 것.

4-3. Deque

최후에 들어온 항목이나 최초 들어온 항목의 어느 것이든 먼저 내보내도록 구성된 것으로 스텍과 큐를 복합한 형태로 선형 리스트중 가장 일반적인 구조로 기억장소의 낭비가 심하다.

4-4. Linked List

링크드(Linked)리스트에는 포인터(Pointer)가 꼭 있어야 하며, 포인터(Pointer)는 자료의 주소를 말한다. 이 구조의 특징은 포인터(Pointer)를 사용하여 자료를 추가 하거나 제거를 빨리 할 수 있다.

(1) 선형 단일 Linked List

(2) 선형 환상 Linked List

(3) 이중 Linked List

(4) 이중 환상 Linked List(Coral Rings)

다중 리스트 방식의 한 변형으로서 각 리스트가 헤드 노드를 가지는 원형 리스트로서 삭제의 경우에 그 레코드의 앞 노드를 몰라 처음부터 다시 찾아야 할 필요가 없는 장점이 있는 리스트 구조이다.

4-5. 행렬(Array)

연접 리스트구조로 논리적 순서에 따라 연속적으로 노드가 나열된 리스트를 의미하며 행렬의 실제 기억장소는 1차원으로 한다.

---

이상 “선형리스트(Linear List)”에 대해 알아 보았습니다.