List, Que,Stack, Map(Dictionary)

1.List

List는 배열의 단점을 보안하기 위한 자료구조다.

기존의 배열은 크기가 고정되어 있어서 데이터를 담은 후 데이터를 추가하거나 삭제하는 방법이 따로 존재하지 않는다.

데이터에 대한 인덱스 값이 고정되어 있기 때문에 삭제하면 해당 공간이 그대로 남아 있어 데이터 낭비가 발생하고 반대로 추가하려고 하면 새로운 배열을 따로 만들어서 하나하나 새로 담아야 하는 단점이 있다.

이러한 배열의 단점을 보안하기 위해 List라는 자료 구조가 나왔다.

List 특징

List는 배열과 달리 중간에 비어 있을 수 없고 서로 이웃한 요소끼리 연결되어 있다. 따라서 어떠한 값이 중간에 제거되었으면 그 다음 요소들을 비어있는 칸으로 한칸씩 위로 올려야 한다.

또한 새로운 데이터가 중간에 하나 추가될 경우, 배열은 해당 인덱스의 값을 덮어쓰지만, List는 해당 인덱스로 부터 한칸씩 뒤로 밀려나고 해당위치에 새로운 값이 추가 된다.

1)배열 리스트 (Array List)

일반적인 배열과 같이 순차적으로 데이터가 쌓이고 인덱스로 내부의 객체를 관리한다. 한번생성되면 고정되어버리는 배열과 달리 가변적으로 변하는 선형리스트 이다.

1)ArrayList

ArrayList에 객체를 추가하면 인덱스 0부터 차례로 저장된다.

ArrayList에서 특정 인덱스의 객체를 제거하게 되면 바로 뒤 인덱스 부터 마지막 인덱스까지 모두 1칸씩 인덱스가 당겨진다.

삽입 역시 특정 인덱스에 객체를 삽입하면 해당 인덱스부터 마지막 인덱스까지 모두 1씩 늘어난다.

ArrayList 사용할때 주의점

ArrlyList는 다음과 같이 순차적으로 쌓여있는 객체들을 일일이 앞으로 또는 뒤로 당기거나 늘리는 방식이기 때문에 데이터 양이 많고 추가나 삭제하는 지점이 초반지점에 가까울 수록 연산이 많이 일어난다.

그렇기 때문에 만약 위의 예시와 같이 삽입이나 삭제 연산이 빈번히 일어날 경우 사용성이 좋지 않다.

2)링크드 리스트(Linked List)

배열은 순차적으로 연결된 공간에 데이터를 나열하는 자료구조이고, 링크드 리스트(Linked List)는 떨어진 곳에 존재하는 데이터를 연결해서 관리하는 자료구조이다.

연결리스트 혹은 단방향 연결 리스트라고도 한다. 그림과 같이 두개의 저장 공간에 데이터를 저장하는 공간, 다음 저장공간을 가리키는 주소값이 들어 있다.

배열처럼 순차적인 인덱스에 데이터가 나열 되어 있지 않고, 서로 다른 메모리 공간에 여기저기 떨어져 있지만 데이터와 함께 다음 데이터가 있는 주소값을 가지고 있기 때문에 이것을 통해서

연결된 모든 데이터를 알 수 있다.

이와 같은 구조를 가지고 있기 때문에 앞서 말한 ArrayList 처럼 중간에 데이터가 추가되거나 삭제 될시 데이터가 들어가거나 삭제된 위치에 따라 인덱스를 맞추기 위해 일일이 앞으로 객체를 당기거나 늘리거나 하지 않아도 된다.

만약 12와 99 사이에 37이라는 데이터를 추가한다면 기존의 arrayList는 해당 위치의 인덱스를 일일이 뒤로 밀고 그곳에 값을 집어넣는 방식을 사용하는 반면 연결 리스트는 데이터에 가지고 있는 주소값만 바꿔주면 된다. 12의 주소값이 들어가는 공간에 99주소값 대신 37의 데이터가 있는 주소값으로 변경하고 37의 주소값이 들어가는 공간에 99가 들어있는 주소값을 가리키도록 연결만 변경해주면 끝난다. ArrayList보다 추가에 대한 작업량이 줄어든다.

삭제할때도 Linked list는 ArrayList 처럼 데이터 삭제후 삭제된 데이터 뒤에 값을 일일이 당길 필요 없이 데이터를 삭제후 삭제된 데이터 주소를 가리키던 것을 99가 가르키던 33의 주소값으로 변경하면 끝난다.

이러한 과정을 보면 알듯이 연결리스트는 배열리스트보다 데이터가 추가되고 삭제될 시 작업량이 줄어든다.

Linked list 사용시 알아야 할 점

데이터와 다음의 데이터를 가지고 올 주소까지 포함하기 때문에 추가적인 데이터 공간이 필요하고, 연결 정보를 찾는 시간이 필요하므로 데이터를 읽는 속도가 ArrayList에 비해 느리다.

따라서 단순 조회는 ArrayList를 사용하는 것이 효율적이고 데이터의 추가 삭제가 빈번히 일어나야 한다면 Linked List를 사용 하는 것이 효율적이다.

그밖에...

이중 연결 리스트(Doubly Linked List),원형 연결 리스트(Circular Linked List),**다중 연결 리스트(Multiply Linked List)**가 존재한다.

2.큐(Que) 와 스택(Stack)

큐와 스택의 공통점은 값이 추가되고 빠져나오는 공간이 정해져 있다. 중간에서 값을 추가하거나 삭제할 수 없다. 이들은 리스트 끝에서 추가 또는 삭제가 일어난다.

큐의 개념

Queue 의 사전적 의미는 1. (무엇을 기다리는 사람, 자동차 등의)줄, 혹은줄을 서서 기다리는 것을 의미한다.

따라서 일상생활에서 놀이동산에서 줄을 서서 기다리는 것, 은행에서 먼저 온 사람의 업무를 창구에서 처리하는 것과 같이

선입선출(FIFO, First in first out) 방식의 자료구조를 말한다.

큐의 특징

정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과는 달리

큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다.

이때삭제연산만 수행되는 곳을 프론트(front),**삽입연산만 이루어지는 곳을 리어(rear)**로 정하여

각각의 연산작업만 수행된다. 이때, 큐의 리어에서 이루어지는 삽입연산을인큐(enQueue)

프론트에서 이루어지는 삭제연산을**디큐(dnQueue)**라고 부른다.

큐의 활용 예시

큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.

• 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
• 은행 업무
• 콜센터 고객 대기시간
• 프로세스 관리
• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 캐시(Cache) 구현

스택의 개념

스택(stack)이란쌓아 올린다는 것을 의미한다.

따라서 스택 자료구조라는 것은 책을 쌓는 것처럼차곡차곡 쌓아 올린 형태의 자료구조를 말한다.

스택의 특징

스택은 위의 사진처럼같은 구조와 크기의 자료를정해진 방향으로만쌓을수 있고,

top으로 정한 곳을 통해서만 접근할 수 있다.

top에는 가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며,

삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다.

스택에서 자료를 삭제할 때도 top을 통해서만 가능하다.

스택에서 top을 통해삽입하는 연산을 'push' , top을 통한삭제하는 연산을 'pop'이라고 한다.

따라서 스택은 시간 순서에 따라 자료가 쌓여서가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는

구조적 특징을 가지게 된다.

이러한 스택의 구조를후입선출(LIFO, Last-In-First-Out) 구조이라고 한다.

그리고 비어있는 스택에서 원소를 추출하려고 할 때 stack underflow라고 하며,

스택이 넘치는 경우 stack overflow라고 한다.

스택의 활용 예시

스택의 특징인 후입선출(LIFO)을 활용하여 여러 분야에서 활용 가능하다.

• 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
• 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
• 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
• 후위 표기법 계산
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

3.Map(Dictionary)

순차적으로 메모리에 데이터를 저장하는 배열과 리스트와는 달리 Map은 Key와 Value로 구성되어 있다.

그림처럼 키와 값이 하나의 쌍으로 연결되어 있어 키를 통해 값에 접근을 할 수 있도록 만들어진 자료 구조이다.

흔히 key와 value가 메칭 되는것을 맵핑(mapping)한다 말한다.

Key를 통해서 값에 접근하는 구조이기 때문에 Key는 반드시 유일한 Key여야하고 중복을 허용할 수 없다.

Map 자료구조의 대표적인 종류

• HashMap

• key와 value의 쌍으로만 구성이 될뿐 자료구조 안에 묶인 쌍들에 대한 순서는 보장할 수 없다.

• 즉, 사용자는 키와 값이 구성되는 위치를 결정 하거나 알 수 없다.

• TreeMap

• key의 값을 이용해 순서대로 정렬하여 데이터를 저장하는 자료구조

• key값을 통한 탐색 뿐 아니라 key값의 정렬을 통한 탐색 등을 하기에 용의 하다.

• LinkedHashMap

• 데이터를 입력한 순서대로 쌓아지며 데이터를 저장하는 자료구조

• 배열, 리스트처럼 인덱싱 접근을 하기에 용의 하다.

'기타' 카테고리의 다른 글

| | Xcode 단축키(0)| 2023.09.16
| | [Nextjs]네이버 문자 SMS 전송 API 포스팅(0)| 2023.08.21
| | Api / REST api/ RESTful api(0)| 2022.12.07
| | Tdd 방법론(0)| 2022.12.07
| | 암호화 기술(0)| 2022.12.07

---

이 글은 제 Tistory 블로그에 처음 게시(2022-12-07)된 글입니다.