Computer Science/Data Structure (3) 썸네일형 리스트형 스택(Stack) LIFO(Last In First Out) 자료구조 먼저 들어간 데이터가 나중에 뽑혀 나오게 저장되는 자료구조. 우리가 이사를 할 때 짐을 싸게 되는데 박스안에 이삿짐을 차곡차곡 쌓아 저장하고 꺼낼때 나중에 넣어서 위에 저장된 짐을 뺴는 것과 같은 형태를 생각하면 이해하기 편하다. 재귀, 시스템 콜, 히스토리를 쌓아 나갈때(ex 인터넷 뒤로가기, 프로그램의 Ctrl+Z) 등에 사용된다. 시간복잡도 삽입 : O(1) 삭제 : O(1) 조회 : O(n) 공간복잡도 O(N) Java에서의 사용법 선언 Queue stack = new Stack(); 삽입 stack.push(items); 삭제 stack.pop(); // 데이터가 없는 상태에서 호출시 EmptyStackException empty 체크 stac.. 링크드리스트(Linked List) 배열은 원소를 삽입, 삭제할때 새로운 저장 공간을 새로 만들거나 원소를 당겨버리는 행동을 하는 등 시간복잡도가 O(n)이 걸리곤 했다. 링크드 리스트는 이 삽입, 삭제에 걸리는 시간을 줄이기 위해 탄생한 자료구조 자료를 저장할때 자료값만 저장하는 것이 아니라 다음 자료가 저장되어있는 위치를 함께 저장시키는 자료구조 저장공간의 크기는 가변적이다. 메모리 공간이 배열과는 달리 연속적으로 구성되어 있지 않다. 원소의 저장이 메모리에 연속으로 들어가는 것이 아니라 원소값과 다음 원소값이 저장되어있는 주소값이 함께 저장되어 있어 그 주소값을 찾아 원소를 탐색해 나간다. 그러므로 배열(Array)의 인덱스(Index)를 통한 접근이 불가능하다. 장점 새로운 원소를 삽입할때 시간복잡도 O(1) 원소를 삭제할때 시간복.. 배열(Array) & ArrayList 연관된 데이터를 하나로 묶어 그루핑해서 관리하기 위해 만들어진 자료구조 배열에서 위치를 가리키는 숫자를 인덱스(Index)라고 부름 인덱스는 0 부터 시작 참조 객체다. 배열을 가리키는 참조 변수는 스택(Stack) 영역에 할당된다. 참조 변수가 가리키고 있는 주소값(Address)는 힙(heap)영역에 생성되는 배열의 주소값이다 특징 선언할때 고정된 크기를 지정해야함. 즉 고정된 크기를 가지게 된다. 메모리 공간이 연속적으로 구성된다. 물리주소와 논리주소가 동일 ⇒ 인덱스(Index)를 활용 가능 장점 인덱스를 통한 접근이 가능하므로 원소를 조회할때 O(1) 인덱스를 통한 접근이 가능하므로 원소를 수정할때 O(1) 단점 배열의 크기가 고정적이라는 말은 다시 말해 더 추가하고 싶다면 더 큰 크기의 배열을.. 이전 1 다음
