카테고리 없음

배열

challnum 2023. 6. 24. 11:47

배열

index(식별자)와 값으로 구성

배열은 크기를 정의하고 변경할 수 없음

초기 정의된 크기대로 연속된 메모리 공간을 가짐

논리적 저장 순서와 물리적 저장 순서가 일치

장점

메모리 공간이 연속적이여서 관리가 편리함

인덱스를 사용해 검색이 빠름

단점

초기 크기 지정(컴파일) 이후, 변경이 되지 않음

만약 데이터가 삭제된다면 빈 공간으로 남아있게 되어 낭비가 생김

 

리스트

동적으로 크기 할당이 가능

장점

포인터가 다음 데이터의 순서를 가리키기 때문에 삽입, 삭제가 빠름 (Linked List)

크기 할당이 동적임

데이터 삭제시, 포인터가 해당 메모리 공간을 가리키지 않으면 되기 때문에 효율적임 (Linked List)

단점

기본 타입은 담을 수 없음 (객체만 가능)

리스트의 5번째 데이터를 검색하기 위해선 1번째 → 2번째 → 3번째 → 4번째 → 5번째 와 같이 순차적으로 포인터를 따라가야 함 (Linked List)

List 종류

list는 Collection 인터페이스를 확장한 인터페이스로 실제로 선언하고 사용하기 위해선 위의 ArrayList와 같이 실제 구현체를 사용해야 합니다.

ArrayList

ArrayList는 배열과 동일하게 인덱스로 객체를 관리하고 크기를 동적으로 변경할 수 있습니다. 만약 기본 저장 용량이나 설정한 용량이 넘어 더 많은 객체가 입력되면 배열의 크기를 증가시킵니다.

  • 확인해봐야 하지만 golang에서와 유사한 개념이라면 ArrayList는 인덱스로 객체를 관리하므로 연속된 메모리 공간을 할당받습니다. 만약 초기 크기가 100인데 그 이상의 객체가 입력되면 150개의 연속적인 메모리 공간을 찾아 할당합니다.

 

배열에서는 중간의 객체가 삭제되면 빈 공간으로 남아 있었지만, ArrayList는 중간 객체가 삭제되면 삭제된 뒤 객체들을 앞으로 이동시킵니다. 동일하게 객체가 추가되면 추가된 이후의 객체들을 뒤로 이동시킵니다.

객체가 삽입, 삭제될 때마다 데이터가 이동하므로 삽입, 삭제에 효율적이지 않습니다.

요약

배열과는 다르게 ArrayList는 동적 크기 할당 가능

배열은 모든 타입을 담을 수 있지만 Array List는 객체만 가능 (int와 같은 기본타입은 오류. int를 담고 싶으면 Integer 객체를 선언해야 함)

조회, 검색이 빠르고 삽입, 삭제는 비효율적

AbstractList 추상 클래스를 상속

LinkedList

ArrayList나 배열과는 다르게 인덱스는 몇 번째 데이터인지 순서의 의미를 의미하고 각 객체에는 포인터로 다음 객체 주소값을 가리키고 있습니다. 또한 논리적 저장 순서와 물리적 저장 순서가 같지 않습니다.

리스트의 5번째 데이터를 검색하기 위해선 1번째 → 2번째 → 3번째 → 4번째 → 5번째 와 같이 순차적으로 포인터를 따라가야 하므로 복잡도가 O(n)이 발생합니다.

 

LinkedList는 삽입, 삭제가 효율적인데 데이터를 삽입 또는 삭제 한 다음, 변경이 일어난 객체의 앞, 뒤 포인터만 변경해주면 됩니다.

Vector

Vector는 ArrayList와 동일한 내부 구조를 가지고 있습니다. 다른 점은 동기화된 메소드로 구성되어 있기 때문에 멀티 스레드가 동시에 Vector의 메소드를 실행할 수 없고 하나의 스레드가 메소드 실행을 완료해야만 다른 스레드가 메소드를 실행할 수 있습니다. 그래서 멀티 스레드 환경에서 안전하게 객체를 추가, 삭제할 수 있습니다. 이것을 스레드에 안전하다고 표현합니다.

요약

동적 크기 할당 가능

ArrayList와 마찬가지로 객체만 담을 수 있음

조회, 검색이 느리고 삽입 삭제가 효율적

AbstractSequentialList 추상 클래스를 상속

멀티 스레드 환경에서는 ArrayList보다 Vector를 사용하는 것이 안전

 

 

 

 

 

스택

 - LIFO 구조, 마지막에 저장된 것을 제일 먼저 꺼냅니다. 후입 선출

큐

 - FIFO 주고, 제일 먼저 저장한 것을 제일 먼저 꺼냅니다. 선입 선출

 

 

스택 메서드

  • push

 Stack에 객체를 저장합니다.

  • pop

 Stack의 맨 위에 저장된 객체를 꺼냅니다.

  • peek

 Stack의 맨 위에 저장된 객체를 반환합니다. Stack에서 꺼내지는 않습니다. 비었을 때 null을 반환합니다.

  • empty

 Stack이 비어있는지 알려줍니다. 있으면 true, 없으면 false를 반환합니다. 

  • search

 Stack에서 주어진 객체를 찾아서 그 위치를 반환합니다. (배열과는 달리 1부터 시작합니다.)

 

 

큐 메서드

  • add

 Queue에 객체를 저장합니다. 

성공하면 true, 실패하면 false를 반환합니다.

  • element

 삭제없이 저장된 요소를 읽어옵니다. peek와 다른 점은 queue가 비었을 때 Exception을 발생시킵니다. (peek()는 null을 반환합니다.) 

  • offer

 Queue에 객체를 저장합니다. 성공하면 true, 실패하면 false를 반환합니다.

  • peek

 삭제없이 읽어옵니다. Queue가 비었을 때 null을 반환합니다.

  • poll

 Queue에서 꺼내옵니다. 비어있으면 null을 반환합니다.

  • remove

 Queue에서 꺼내옵니다. 비어있으면 예외를 발생시킵니다.