[ Java ] 자료구조

 

 

자료구조

💡 Iterator 
순서(인덱스)가 없는 데이터의 집합 전체를 순회해주는 for문과 같은 역할을 해서 전체 데이터를 출력 ( 사용 : Set, Collection )

 

자료구조 이미지로 확인해보기

Data Structure Visualization

 

1. 자료구조란?

• 자료구조(data structure)

데이터를 효율적으로 사용할 수 있도록 구조를 만들어서 저장해둔 것

 

1-1. 자료구조의 종류

• 리스트(list) : 배열 리스트(array list), 연결 리스트(linked list)로 세분됨
• 스택(stack)
• 큐(queue)
• 해쉬 테이블(hashtable)
• 집합(set) * 엄밀히 말하면 자료구조가 아님

자바에서 자료구조 - list ,map,set

특성에 맞게 자료구조를 선택

 

---

 

2. List

• 순서가 있다. 중복이 허용된다.
• 선형 구조를 갖는 리스트는 배열보다 많이 사용★

2-1. ArrayList

💡 ArrayList  list = new ArrayList();

 

< 데이터형 > → 재내릭 : 타입 파라미터 → 해당 타입만 들어갈 수 있게 선언해줌.

String /Integer/Byte/Short/Long /Char/

메서드	의미	예시
add	데이터 값 추가	list.add(”포도”)
	원하는 인덱스에 값 추가	list.add(1,”수박”);
remove	데이터 삭제	list.remove(0);
		list.remove(”포도”);
set	데이터 교체	list.set(0,”오렌지”);
get	데이터 값 출력	list.get(2);
subList	필요한 데이터만 추출	listNumber.subList(0, 2)
size	데이터 갯수 출력	list.size();
clear	데이터 전체 삭제	list.clear();
indexOf	몇 번에 있는지	문자열.indexOf(list);
Collections.sort(리스트);	오름차순 정렬	Collections.sort(list);
Iterator listIter = list.iterator();	리스트 데이터 전체 출력 방법
addAll	리스트 병합 (리스트 + 리스트)	listNumber.addAll(listNumber2);

 

 

- List 생성

//1.정수형 객체만 저장 가능한 리스트
ArrayList<Integer> numbers1 = new ArrayList<Integer>();

// 2. 초기 용량 지정 numbers2
ArrayList<Integer> numbers2 = new ArrayList<Integer>(20);

// 3. 배열을 넣어서 생성
    //Arrays.asList(10,20,30) 배열 생성 
ArrayList<Integer> numbers3 = new ArrayList<Integer>(Arrays.asList(10,20,30));

// 4. 다른 컬렉션으로 부터 그대로 요소를 받아와 사용. 
ArrayList<Integer> numbers4 = new ArrayList<Integer>(numbers3);

 

- List 내부 메서드

List<String> list = new ArrayList<String>();
list.add("사과");
list.add("포도");
list.add("수박");

//출력방법 1
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}
System.out.println("==========================");
//출력 방법2 .Iterator   (List,Map,Set)--> 통용해서 출력 
Iterator<String> iter = list.iterator(); //Iterator로 데이터형 변환

while (iter.hasNext()) { // 있는 값확인
    System.out.println(iter.next());
}


System.out.println(list.subList(0, 2));
//[사과, 포도]

 

- List 병합

 

// 동적할당		
List<Number> listNumber = new ArrayList<Number>();
listNumber.add(10);
listNumber.add(20);
listNumber.add(30);
System.out.println(listNumber.size());

List<Number> listNumber2 = new ArrayList<Number>();
listNumber2.add(60);
listNumber2.add(70);
listNumber2.add(80);


//리스트 병합 = 리스트 + 리스트 
listNumber.addAll(listNumber2);
System.out.println(listNumber.size()); // 6개

 

 

2-1. ArrayList VS LinkeList

ArrayList(선형 리스트 )

• 연속하는 메모리 공간에 저장
• 내부적으로 Object[] 배열을 이용하여 요소를 저장한다.
• 배열을 사용하기 때문에 인덱스를 이용하여 빠르게 접근이 가능하다. 
• 데이터 적재량에 따라 가변적으로 공간을 늘리고 줄인다.
• 데이터를 중간에 삽입/삭제 시 ,빈공간이 생기지 않도록 내부에서 인덱스를 조정하는 과정이 있어 동작이 느리다.
• 조회기능에 적합한 데이터 구조 이다.   전체를 순회해서 데이터 값을 출력하는 경우. (ex.글 목록)

 

LinkeList(연결 리스트)

• 이전 , 다음 데이터에 대한 정보를 가지고 있다. (다음 노드를 가리키는 포인터)
• 데이터 구조에 수시로 수정 삭제가 발생할 일이 많을 때 사용(메모리 참조하는 구조) , 추가한 순서대로 값이 저장(속도가 더 빠름)
• 추가/ 삭제 시 연결을 끈고 다시 연결한다.
• 단점  임의의 요소에 대한 접근 성능은 좋지 않다. 
• 데이터의 저장 순서가 유지되고 중복 허용

 

• 리스트 추가  :  addFirst(Object),addLast(Object),  add(Object), add(index,Object), addAll(Collection c)
• 리스트 제거 : removeFirst(), removeLast(),remove(Object),remove(index)

//라이브러리에서 제공하는 생성자를 이용
LinkedList<Integer> list1 = new LinkedList<Integer>();
LinkedList<Integer> list2 = new LinkedList<Integer>(Arrays.asList(1,2));


LinkedList<String> list3 = new LinkedList<String>(Arrays.asList("J","A","B"));
//  addFirst(Object),addLast(Object), 
// add(Object), add(index,Object), addAll(Collection c)
System.out.println(list3);

list3.addFirst("R");
System.out.println(list3);

list3.addLast("t");
System.out.println(list3);

// 배열 출력하기 
Iterator<String> it = list3.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

 

---

 

3.  Set

💡 TreeSet list = new TreeSet ();

• 집합으로 중복 x
• 유일한 값들을 관리할때 사용 (ex.주민번호)
• 순서가 없다. —> get을 통해 가져올 수 없다… Iterator를 통해서만 리스트를 뽑을 수 있다.
• HashSet, TreeSet
• 오름차순으로 값을 정렬해 가지고 있으며
• 다른 set보다 대량의 데이터를 검색할 시 훨씬 빠르다.

메서드	의미	예시
add	데이터 값 추가	list.add(”포도”)
System.out.println(list);	데이터 전체 출력

 

TreeSet<Integer> listTree = new TreeSet<Integer>();
System.out.println("-------------------");
for (int i = 0; i < 6; i++) {
    listTree.add((int)(Math.random()*45)+1);
}

System.out.println(listTree);

 

---

 

4. Map

Hashtable(Properties), HashMap, TreeMap

💡 Map<String, Integer> map = new HashMap<String, Integer>();

• < key, value > 한 개의 쌍으로 표현 (ex) 이름, 전화번호
• 순서가 없다.

메서드	의미	예시
put	데이터 추가	map.put("홍길동" , 01011112222);
get	데이터 값 확인	map.get("홍길동"); map.get(01011112222);
contentKey	데이터에 해당 key 값이 있는지 여부	contentKey(”홍길동”)
contentsValue	데이터에 해당 value 값이 있는지 여부	contentsValue(01011112222)

 

★ 데이터값 출력

데이터 값을 출력하려면 Map 데이터 형에서 Set 또는 Collection 데이터 형으로 변경해야 한다.

이때 set 메서드를 사용할수 있는 전체 값( .entrySet() )과 키( .keySet() )값은 Set 타입으로 변경하여 출력.

value값은 메서드( .values() )를 사용해 Collection 타입으로 변경하여 출력한다.

예시

 

1. 전체 출력 key, value→ Iterator 를 통해 각각 출력 가능
2. //전체 데이터값 출력 (key,value) Set set = map.entrySet(); Iterator iter = set.iterator(); //key,value while (iter.hasNext()) { //map의 안에 value 와 키의 묶음 하나 -> 데이터타입은 Map.Entry (.)점 -> 내부 클래스 , 내부 인터페이스 //Map의 내부 클래스 Entry Map.Entry<String, String> e = (Map.Entry<String, String>)iter.next(); System.out.println("key: " + e.getKey() +" , value: " + e.getValue()); }
3. Set타입으로 변경 → entrySet() 메서드를 사용하면 전체를 뽑을 수 있다.
4. key 값 만 출력

    Set<String> keyinput = list.keySet();
    System.out.println(keyinput);

5. Set타입으로 변경 -> keySet() 메서드를 사용하여 추출 가능.

1. value값 만 출력

    Collection<Integer> listScore = list.values();
    System.out.println(listScore);

2. Collection 타입으로 변경 → values() 메서드를 사용하여 추출 가능.

 

Collections

최대값→ int max= Collections.max(listScore);
최소값 → int min= Collections.min(listScore);

 

---

 

5.  hashtable

가장 처음 넣은 것이 가장 먼저 나오도록 하는 것

 

---

 

 

6. Stack

💡 Stack s = new Stack();

FILO(First-In-Last-Out : 선입후출)" 혹은 "LIFO(Last-In-First-Out : 후입선출이라고한다. 

• 마지막에 넣은 것을 가장 먼저 나오도록 하는 것
• ex) 브라우저 뒤로가기, 자판기

 

명령어	의미	예시
push	데이터 추가	list.push(”포도”);
pop	데이터 값 제거	list.pop();

//stack >> push,pop
Stack<Integer> s = new Stack<Integer>(); //stack 자료구조

s.push(1);
s.push(2);
s.push(3);
System.out.println("=========================stack");
while (!s.isEmpty()) { //isEmpty 비어 있는지 안 비어있는지 확인.

    System.out.println(s.pop()); //pop뽑아내기

}

 

 

예제 ) 괄호가 일치/불일치 판단.

• package kosta.data; import java.util.Scanner; import java.util.Stack; public class StackExam { public static void main(String[] args) { // 키보드로부터 수식을 입력 //((2+3)+10) ==> 괄호가 일치/불일치 판단... Scanner sc = new Scanner(System.in); Stack<String> stack = new Stack<String>(); System.out.println("수식 입력 : "); String str = sc.nextLine(); try { for (int i = 0; i < str.length(); i++) { char ch = str.charAt(i); if (ch == '(') { stack.push(ch + ""); }else if(ch == ')') { stack.pop(); } } if (stack.isEmpty()) { System.out.println("괄호가 일치"); }else { System.out.println("괄호가 불일치"); } } catch (Exception e) { System.out.println("괄호가 불일치"); } } }

Stack 문제 

문제

Stack은 "더미"란 뜻을 가진다.
책 더미, 신문 더미 등에 사용하는 단어이다. 
책 더미를 예로 들어 보자. 
책 더미를 쌓았다고 했을 때, 이 책 더미에서 책을 가져오는 가장 정상적인 방법은 제일 위에 있는 책을 가져오는 방식이다.

다시 말하면 가장 먼저 들어간 책은 가장 나중에 꺼낼 수 있을 것이다.
이런식으로 자료가 가장 밑에 쌓이고(입력). 자료를 가져올 때(출력)는 가장 위(최근)의 자료를 가져오는 자료구조를 Stack하고 한다. 
이러한 Stack의 특징 때문에 흔히 "FILO(First-In-Last-Out : 선입후출)" 혹은 "LIFO(Last-In-First-Out : 후입선출)"라고 한다.

그림과 같이 Stack을 설계하고 다음의 처리조건에 맞는 출력을 하시오.

처리조건

주어진 명령은 다음의 3가지이다.
1. "i a"는 a라는 수를 스택에 넣는다. 이때, a는 10,000 이하의 자연수이다.
2. "o"는 스택에서 데이터를 빼고, 그 데이터를 출력한다. 만약 스택이 비어있으면, "empty"를 출력한다.
3. "c"는 스택에 쌓여있는 데이터의 수를 출력한다.

입력

첫 줄에 N이 주어진다. N은 주어지는 명령의 수이다. (1≤N≤100)
둘째 줄부터 N+1줄까지 N개의 명령이 주어지는데, 한 줄에 하나씩 주어진다.

출력

각 명령에 대한 출력 값을 한 줄에 하나씩 출력한다.
출력내용이 하나도 없는 경우는 주어지지 않는다.

code

package jungolEx.stack;

import java.util.Scanner;

public class stackEx01 {

	private static Scanner in;
	public static int[] result;
	
	public static void main(String[] args) {
		//https://jungol.co.kr/problem/1102
		
		in= new Scanner(System.in);
		
		
		// 스텍
		int stack1[] = new int[100];
		// 스텍 층 - 쌓인 데이터 수 채크 
		int nIndex =0;
		
		//명령어 수 
		int n = in.nextInt();
		//명령
		String cmd; 
		
		in.nextLine(); // 개행문자 제거
	
		
		for(int i=0; i < n ;i++) {
			
			cmd = in.nextLine(); 
			
			// insert
			if('i' == (cmd.toCharArray()[0])) {
				System.out.println("0");
				stack1[nIndex++] = cmd.toCharArray()[2];
				
			}
			// out
			else if("o".equals(cmd)) {
				System.out.println("1");
				if(nIndex == 0) System.out.println("empty");
				else System.out.println( stack1[--nIndex] );
				
			}
			//count 
			else if("c".equals(cmd)) {
				System.out.println("2");
				System.err.println(nIndex);
			}
			
		} // end for 
	}
}

 

 

---

 

7. Queue

• 선입선출(FIFO - First In First Out)
• 가장 처음 넣은 것이 가장 먼저 나오도록 하는 것
• ex) 배달 시스템

 

명령어	의미	예시
offer	데이터 추가	list.offer(”포도”);
poll	데이터 값 제거	llist.poll();

//Queue >> offer ,poll
LinkedList<Integer> q = new LinkedList<Integer>(); //Queue 자료구조
q.offer(1);
q.offer(2);
q.offer(3);
System.out.println("=========================Queue");
while (!q.isEmpty()) {
    System.out.println(q.poll());
}

 

 

---

 

8. 정렬(sorting)

List , Set은 인터페이스로 만들어진 데이터 집합…

해당 데이터의 정렬을 변경해주기 위해서는 인터페이스를 사용하여 변경 필요.

Collections.sort(리스트명);  >> 정렬

• 기본 정렬 조건 : 인터페이스 Comparable > compareTo() 오버라이딩
• package kosta.data; public class Member3 implements Comparable<Member3> { String name; int age; String address;

    public Member3(String name, int age, String address) {
        super();
        this.name = name;
        this.age = age;
        this.address = address;
    }


    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    public String getAddress() {
        return address;
    }
    public void setAddress(String address) {
        this.address = address;
    }

    @Override
    public int compareTo(Member3 o) {
        if (age < o.age) {
            return -1; // 안움직임
        }else if(age > o.age){
            return 1; // 변화
        }
        return 0;
    }


}
```

```java
package kosta.data;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class MemberMain3 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        List<Member3> mlist = new ArrayList<Member3>();
        mlist.add(new Member3("길동이", 20, "서울"));
        mlist.add(new Member3("홍씨", 30, "남양주"));        
        mlist.add(new Member3("박씨", 10, "경기"));


        Collections.sort(mlist);

        for (Member3 m : mlist) {
            System.out.println(m.getAge());
        }

    }

}
>>결과값 : 박,길,홍
```

• 정렬기준을 변경 : 인터페이스 Comparator -> compare() 오버라이딩.compareTo //사전적으로..
  //0 -> 서로같다
  //음수 -> aa.compareTo(BB);
  //양수 -> BB.compareTo(aa);
• //이름을 기준으로 정렬될 수 있게 변경. Collections.sort(mlist, new Comparator<Member3>() { @Override public int compare(Member3 o1, Member3 o2) { if (o1.getName().compareTo(o2.getName()) > 0) { //o1이더 크다.. return 1; //자리변경 }else if(o1.getName().compareTo(o2.getName()) < 0) { //o2이더 크다.. return -1; } return 0; } }); >> 결과값 : 길 , 박, 홍