선형 자료구조

• 선형 자료구조
  • Array
  • List
  • HashTable
  • Queue
  • Stack

 

선형 자료구조

하나의 자료 뒤에 하나의 자료가 존재하는 것

비선형 자료구조: 하나의 자료 뒤에 여러 개의 자료가 존재하는 것

 

 

Array 배열

1. 데이터를 나열하고 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조

2. 같은 종류의 데이터를 효율적으로 관리하기 위해 사용

3.

장점	단점
-검색이 빠르다 -연속적이기 때문에 메모리 관리가 용이	-배열의 크기를 컴파일 이전에 정해야한 다. -중간에 데이터 삽입, 삭제가 어렵다

4. 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합

5. 순서가 있고 중복 허용

탐색에 o(1)이 되어 램덤 접근 가능, 삽입과 삭제는 o(n) 걸림 

 

랜덤접근과 순차적 접근

랜덤접근(직접 접근): 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능

순차적 접근: 데이터를 저장된 순서대로 검색

List 리스트

1. 순서가 있는 엘리먼트의 모임으로 배열과 다르게 빈 엘리먼트를 허용하지 않는다.

2. 불연속적으로 메모리 공간을 차지하고, 포인터를 통해 데이터에 접근하다.

3.

장점	단점
-중간에 데이터 삽입, 삭제가 쉽다 -리스트 크기가 정해져있지 않다. -불연속적으로 메모리 관리가 편리하다.	-검색 성능이 좋지 않다. - 포인터를 통해 데이터를 가리키기 때문에 추가적인 메모리 공간이 발생한다.

 

List와 ArrayList 차이

List	ArrayList
-인터페이스 -List안에 ArrayList, LinkedList등이 포함 List list = new ArrayList();	-클래스

 

ArrayList

1.배열을 기반으로 데이터 저장 => index를 가진다.

2. 검색이 빠르지만 삽입,삭제가 느리다.

LinkedList

1. 데이터가 노드로 구성되어 연결이 되는 구조로 양방향 연결 리스트

2. 데이터는 포인터와 주소를 사용하여 연결 

3. ArrayList보다 검색이 느리지만 삽입,삭제가 이루어지는 경우 용이함

 

 

배열과 연결 리스트 차이

데이터 추가 삭제는 연결 리스트가 더 빠르고 배열은 느리다. 

탐색은 배열이 빠르고 연결리스트가 느림 

 

 

HashMap

1. key: value 형태의 데이터 구조

2.Map 인터페이스를 구현한 구현체

3.

장점	단점
-중복제거하는데 용이 -검색용이	-순서를 보장하지 않음 -해시 함수를 사용해 충돌 발생가능성

 

 

HashTable

1. key: value 형태의 데이터 구조

2. 동작 원리 : 해시함수를 통해 배열에 키에 대한 데이터를 저장할 수 있는 주소(인덱스)를 계

 - 해시함수: 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수

키를 해시 함수로 계산하여 그 값을 배열의 인덱스로 사용

3.

장점	단점
-저장,탐색 속도가 빠름 ( O(1)) -키와 해시값이 연관성이 없어 보안에도 많이 사용	-다소 많은 저장공간이 필요하다. -동기화로 인해 연산이 느려질 수 있다. -여러 키가 해당하는 주소가 동일할 경우, 충돌을 해결하기 위한 별도의 자료구조가 필요

 

Hash Table vs Hash Map

공통점: hash함수를 이용해 데이터 저장, key-value형식으로 데이터 저장

차이점

HashMap	HashTable
동기화 지원 x null 허용	동기화지원 o null 허용 x

동기화:

하나의 공유되는 자원에 대해서 동시에 접근하는 것을 제한하는 것, 순차적으로 접근할 수 있도록 해주는다.

java에서는 synchronized키워드 사용

 

 

hash 충돌 해결법

서로 다른 값을 가진 key가 해시 테이블의 한 주소에 매핑되는 경우 충돌이 발생한다. hashing을 해서 삽입하려고 했으나 이미 다른 원소가 자리를 차지하고 있는 상황이다. 이럴 경우 오버 플로우 발생

 해결 방법

1. Open Addressing Method

-선형탐색: 충돌이 일어난 바로 뒷바리로 값을 넣어준다. n칸 옆을 검사

-이차조사법: 충돌이 일어나면 2차 방정식을 이용해서 위치를 구해 값을 넣어준다.n^2칸 옆을 검사

-이중해싱: 두 개의 함수를 시용하여 하나의 함수는 최초 해시값을 구하고 다른 함수는 해시 충돌이 일어났을 경우 이동할 쪽을 구할 때 사용

-재해싱: 해시테이블의 크기를 늘리고 새로운 해시 테이블의 크기에 맞춰 다시 모든 데이터를 해싱

2. Closed Addressing Method

-체이닝: 해시 테이블 자체는 포인터 배열로 만들고 같은 버켓의 해당하는 데이터들을 체인 형식으로 만들어 연결하는 방식

버킷 내에 연결리스트를 할당하여 버킷에 데이터를 삽입 해시 충돌이 발생하면 연결리스트로 데이터들을 연결
- 체이닝의 경우 버킷이 꽉 차더라도 연결리스트로 계속 늘려가기에 데이터의 주소값은 바뀌지 않음

https://j3sung.tistory.com/759

 

 

Stack 스택

 

1.LIFO(Last In First Out) 동작: 마지막에 추가된 데이터가 가장 먼저 나옴

 

2.

push: 데이터 추가

pop: 데이터 제거

peek: 스택의 최상단 값 확인

size() : 스택에 들어있는 데이터의 개수  

Stack<String> st = new Stack<>();

//데이터 추가
st.push("data1");
//데이터 꺼내기
st.pop();
//최상단 값 출력(데이터를 꺼내지 않음)
st.peek();
//스택 사이즈 확인
st.size();

 

 

 

Queue 큐

1.FIFO(First In First Out)동작 : 먼저 들어온 데이터가 가장 먼저 나감

 

2. 

Enqueue: 큐 맨 뒤에 데이터 추가 -> offer, add

Dequeue: 큐 맨 앞쪽의 데이터 삭제 -> poll, remove

peek: 데이터 확인 -> peek,element

 

3. 그래프의 넓이 우선 탐색(BFS)에 사용

 

4. 컴퓨터 버퍼에서 주로 사용, 계속 입력되어 처리 하지 못할 때 큐를 만들어 대기시킴

Queue<String> que = new LinkedList<String>();

//데이터 추가
que.add("data1");
//데이터 삭제

que.poll();
que.remove();
que.remove("data1");

que.clear();

5.poll() 과 remove() 의 다른점

poll()은 대기열이 비어있다면 null을 반환,

remove()은 대기열이 비어있으면 NoSuchElemnet에러를 반환

 

6. Priority Queue 우선순위 큐: 우선순위가 높은 것을 꺼냄

-숫자를 저장한 우선순위 큐는 숫자가 작을수록 우선순위가 높다

-숫자 외의 데이터는 객체의 크기를 비교할 수 있는 방법을 사용하여 비교(Comparator, comparable)