[스터디 1주차] 선형자료구조

1. 선형 자료구조

사진 출처

=> 자료들을 순차적으로 나열시킨 자료구조
배열, 연결리스트, 스택, 큐가 있다.

2. 배열

자바에서 배열의 표현 방법

int[] odds = {1, 3, 5, 7, 9};
or
int[] odds = new int[3];

자료형 [] 형태로 나타내는데, 이는 배열자체가 자료형인것이 아니라 자료형들의 모임을 나타내는 것이다.

배열의 특징
1. 길이가 고정되어있다.
2. 다차원 배열 가능
3. 연속된 메모리의 공간 => 메모리 관리가 편하지만 크기가 고정되어있기때문에 삭제시 메모리 낭비가 된다.

3. 리스트

java에서 List 인터페이스를 구현 한 클래스

• ArrayList
• LinkedList
• Vector
• Stack

1. Array List
   

  ArrayList<Integer> arrList = new ArrayList<Integer>();

자주쓰는 메소드 add, get, isempty, size, remove(인덱스 또는 값으로 삭제할 수 있다)

배열과의 차이점
배열보다 느리지만 배열의 조작이 많이 필요한 경우 쓴다.
arraylist는 크기가 동적으로 늘어난다.

2. Linked List

LinkedList<String> lnkList = new LinkedList<String>();

• 노드의 포인터 부분으로 서로 연결시킨 리스트
• Array List가 배열을 이용하여 요소를 저장함으로 발생하는 단점을 극복하기 위해 고안됨 = 삽입과 삭제가 빈번한 프로세스에서 사용함
  => 배열은 요소가 순차적으로 저장됨. 연결 리스트는 비순차적으로 , 요소사이를 link로 연결함. 노드의 추가와 삭제가 위치정보의 수정만으로 가능함(배열은 추가한후 뒤로 물리고, 삭제한후 뒤의 원소들을 앞으로 모두 당기는 과정이 필요)
• 순차적 접근만 가능함 (탐색에서 시간이 오래걸린다)

메소드는 arraylist와 거의 같다.

3. vector
   Arraylist와 같은 동작을 수행함
   호환성을 위해서만 남아있으므로 arraylist를 사용하는게 좋다.
   

4. Stack

선형 구조의 메모리 공간에 데이터를 저장하면서 후입선출(LIFO)를 따름

  Stack s=new Stack();

• 메소드
  push(E item) : 스택의 맨위에 객체 삽입
  peek() : 스택의 맨위의 것 반환 (스택에서 pop하는것은 아님)
  pop() : 스택의 맨위의 것 반환 후 제거
  empty() : 스택이 비어있는지 boolean으로 리턴
  search(Object o) : 전달된 객체가 존재하는 위치의 인덱스 반환 (인덱스 1부터 시작)

5. Queue

스택과 달리 별도의 인터페이스 형태로 제공 됨
리스트의 한 방향에서 삽입작업이, 반대편에는 제거 작업이 이루어지는 자료구조 선입선출(FIFO)를 따름

  Queue q=new LinkedList<>();

• 메소드

offer(E e) : 큐의 맨뒤에 주어진 객체를 넣음
add(E e) : 큐의 맨뒤에 주어진 객체를 넣음 성공여부에 따라 true나 exception 반환
peek() : 큐의 맨앞에 있는(제일 먼저 저장된) 요소 반환 비었을 시 null
poll() : 큐의 맨앞에 있는 요소 반환 후 제거
remove() : 큐의 맨앞에 있는 요소 제거
element() : 큐의 맨앞에 있는 요소 반환

REFERENCE
링크텍스트
ARRYALIST
링크텍스트
링크텍스트

문제풀기

링크텍스트
링크텍스트