[Java] 자료구조(선형구조와 비선형구조)

선형구조: 자료를 구성하는 데이터를 순차적으로 나열시킨 형태

ex) 리스트(배열),연결리스트,덱, 스택, 큐

 

비선형구조: 하나의 자료 뒤(안)에 여러개의 자료가 존재할 수 있는것

ex) 트리, 그래프

 

선형구조

[리스트(배열Array)]

- 인덱스를 가지고 있으며, 순차적으로 데이터가 삽입/삭제될 수 있는 형태의 자료 구조

- 가장 보편적이고 단순한 선형 리스트 구조이자 정적인 자료 구조

- 항목을 순차적으로 연속적인 기억장소에 배당하므로 자료의 물리적 위치와 논리적 위치가 동일

- 데이터를 순차적으로 삽입하거나 삭제를 해야할 때 가장 효과적

장점	단점
- 삽입, 삭제가 발생하지 않는 정적인 응용 업무에서 처리해야할 자료가 언제나 같은 개수를 유지할 경우 기억장소를 100% 활용 가능 - 인덱스를 통한 조회의 속도가 빠름	- 메모리 사용이 비효율적 - 프로그램 실행 전에 최대 크기로 배열 크기 선언 필요 - 배열의 모든 요소를 연속적으로 메모리에 저장 - 배열의 요소를 삽입/삭제 후에 연속적인 물리 주소를 유지하기 위한 작업 필요 - 요소를 삭제해도 크기의 변화 없음

package ArrayList;

import java.util.ArrayList;

public class arraylist생성 {

	public static void main(String[] args) {
		// 1. ArrayList 생성
		// 크기지정(기본값 : 10)
		ArrayList<String> al = new ArrayList<String>(7);
		
		//2. 요소 삽입
		//2-1. 맨마지막 자리에 삽입
		al.add("python"); //0
		al.add("java"); //1
		al.add("javascript"); //2
		
		// 2-2. 특정 자리에 삽입(인덱스번호(int),삽입할 데이터)
		al.add(1,"c++");
		
		//3. 요소 개수
		int n = al.size();
		System.out.println(n);
		
		//4. 특정 위치의 요소 알아내기
		System.out.println(al.get(1));
		
		for(String s : al) {
			System.out.println(s);
		}
		
		//5. 요소 삭제
		//5-1. 특정 인덱스에 요소 삭제
		al.remove(2);
		
		//5-2. 전체 삭제
		al.clear();
		
		for(String s:al) {
			System.out.println(s);
		}
		

	}

}

<뮤직리스트 만들기>

---

연결 리스트[Linked List]

- 차례로 연결된 노드를 표현하는 동적인 자료구조로 단방향과 양방향이 존재

- 노드와 링크로 구성

   - 노드는 실제 정보를 담고 있는 하나의 단위

   - 링크는 노드 간의 위치 정보를 저장 -> 연결 리스트의 순서를 유지할 수 있도록 하는 연결고리 역할을 담당

장점	단점
- 동적으로 메모리 사용 가능 - 메모리 사용이 효율적 -> 필요가 없으면 메모리 할당을 해제 - 데이터 재구성이 용이 -> 데이터 추가/삭제 빠름 - 대용량 데이터 처리에 적합	- 특정 위치 데이터 검색이 느림 - 메모리의 추가적 사용 필요