멀티캠퍼스 백엔드 과정50일차-51일차[8월 16일-17일] - 자료구조, 알고리즘 스택과 큐, 배열, arrayList, LinkedList

GoldenDusk·2023년 8월 17일
ArrayListlinkedlist배열스택알고리즘큐
0

멀티캠퍼스 백엔드 과정

목록 보기
44/60
post-thumbnail

월 화는 휴강

알고리즘

🍐 알고리즘이란?

  • 어떤 문제를 해결하기 위한 절차로, 명확하게 정의되고 순서가 있는 유한 개의 규칙으로 이루어진 집합
  • 알고리즘을 아무리 명확하게 정의해도 변숫값에 따라 결과가 맞기도 하고 틀리기도 한다면 올바른 알고리즘이라 수 없다

🍐 조건 판단과 분기

import java.util.Scanner;

public class Max2 {

    // 세 정수 중 최댓값을 판단하는 메소드를 정의
    static int maxJudge(int a, int b, int c) {
        int max = a;

        if (b > max) {
            max = b;
        }
        if (c > max) {
            max = c;
        }

        return max;
    }
    
    static int min3Judge(int a, int b, int c) {
        int min = a;

        if (b < min) {
            min = b;
        }
        if (c < min) {
       	 min = c;
        }
        return min;
    }
    
    static int min4Judge(int a, int b, int c, int d) {
    	int min = a;
    	
    	 if (b < min) {
             min = b;
         }
         if (c < min) {
        	 min = c;
         }
         if (d < min) {
        	 min = d;
         }

         return min;
    	
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("네 정수의 최댓값을 구합니다.");
        System.out.print("a의 값 입력: ");
        int a = in.nextInt();
        System.out.print("b의 값 입력: ");
        int b = in.nextInt();
        System.out.print("c의 값 입력: ");
        int c = in.nextInt();
        System.out.print("d의 값 입력: ");
        int d = in.nextInt();

        // maxJudge 메소드를 호출하여 최댓값을 계산하고 출력합니다.
        int result = maxJudge(a, b, c);
        System.out.println("최댓값: " + result);
        result = min3Judge(a, b, c);
        System.out.println("최솟값: " + result);
        result = min4Judge(a, b, c, d);
        System.out.println("최솟값: " + result);
        
    }
}
  1. 예제 2
import java.util.Scanner;

public class Main {
    public static void main(String[] args)
	{
        Scanner in = new Scanner(System.in);
        // 높이 입력 받기
        int n = in.nextInt();
        // 종류 입력받기
        int m = in.nextInt();
        
        if (n <= 100) {
            if (1 <= m && m <= 3) {
                switch (m) {
                    case 1: //1일때
                        for (int i = 1; i <= n; i++) {
                            for (int j = 1; j <= i; j++) {
                                System.out.print("*");
                            }
                            System.out.println();
                        }
                        break;
                    case 2: // 2일 때
                    for(int i=0;i<n;i++){
                        for(int j=i;j<n;j++){
                            System.out.print("*");
                        }
                        System.out.println();
                    }
                        break;
                    default: // 3일떄
                       for(int i=0;i<n;i++){
                for(int j=i;j<n-1;j++){
                    System.out.print(" ");
                }
                for(int j=0;j<i*2+1;j++){
                    System.out.print("*");
                }
                System.out.println();
            }
                }
            }
        }
        else {
            System.out.println("INPUT ERROR");
        }
    
	}
}

🍐 별찍기

public class StarEx
{

	static void star01()
	{
		for (int i = 0; i < 4; i++)
		{ // 행 출력

			for (int j = 0; j < 4; j++)
			{
				System.out.print("*");
			}
			System.out.println();

		}
	}
    
	static void star02()
	{
		for (int i = 0; i < 4; i++)
		{
                                       //빈칸의 갯수만큼 별 출력 
			for (int j = 0; j <= i; j++)
			{
				System.out.print("*");
			}
			System.out.println();

		}
	}
	
	static void star03() { 
		for (int i = 0; i < 4; i++)   //4줄 생성 
		{
                                       //빈칸의 갯수만큼 별 출력 
			for (int j = 3; j >= 0; j--)
			{
				
				if(i<j) {
					System.out.print(" ");
				}else {
					System.out.print("*");
				}
				
			}
			System.out.println();

		}
	}
	
	static void star04() { 
		for (int i = 4; i > 0 ; i--)   //4줄 생성하면서 빈칸 하나씩 줄어들게 하기 
		{
                                       //빈칸의 갯수만큼 별 출력 
			for (int j = 0; j < i; j++)
			{
				System.out.print("*");
			
			}
			System.out.println();

		}
	}
	
	static void star05() { 
		for (int i = 0; i > 4 ; i++)   //4줄 생성
		{
                                       //j가 i보다 작으면 
			for (int j = 0; j < i; j++)
			{
				System.out.print(" ");
			
			}
			
			for (int j = 3; j >= i; j--)
			{
				System.out.print("*");
			
			}
			System.out.println();

		}
	}
	
	
	static void star06() { 
		for (int i = 0; i < 4 ; i++)   //4줄 생성
		{
                                       //j가 i보다 작으면 
			for (int j = 0; j < 3-i; j++)
			{
				System.out.print(" ");
			
			}
			
			for (int j = 0; j <2*i+1; j++)
			{
				System.out.print("*");
			
			}
			System.out.println();

		}
	}
	
	static void star07() { 
		for (int i = 0; i < 4 ; i++)   //4줄 생성
		{
                                       //j가 i보다 작으면 
			for (int j = 1; j <=i; j++)
			{
				System.out.print(" ");
			
			}
			
			for (int j = 7; j >=i*2+1; j--)
			{
				System.out.print("*");
			
			}
			System.out.println();

		}
	}
	
	public static void main(String[] args)
	{
              star01();
              star02();
              star03();
              star04();
              star05();
              star06();
              star07();
              
	}
}

🍐 스택

스택과 큐에 대한 정리

스택과-큐 정리한 내 블로그 글

  1. IntStackTest
// int형 고정 길이 스택의 사용 예

import java.util.Scanner;

class IntStackTester {
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        IntStack s = new IntStack(64);    // 최대 64 개를 푸시할 수 있는 스택

        while (true) {
        	System.out.println(); // 메뉴 구분을 위한 빈 행 추가
            System.out.printf("현재 데이터 개수: %d / %d\n", s.size(), s.getCapacity());
            System.out.print("(1)푸시　(2)팝　(3)피크　(4)덤프　(0)종료: ");

            int menu = stdIn.nextInt();
            if (menu == 0) break;

            int x;
            switch (menu) {
             case 1:                                // 푸시
                System.out.print("데이터: ");
                x = stdIn.nextInt();
                try {
                    s.push(x);
                 } catch (IntStack.OverflowIntStackException e) {
                    System.out.println("스택이 가득 찼습니다.");
                }
                break;

             case 2:                                // 팝
                try {
                     x = s.pop();
                    System.out.println("팝한 데이터는 " + x + "입니다.");
                 } catch (IntStack.EmptyIntStackException e) {
                    System.out.println("스택이 비어있습니다.");
                }
                break;

             case 3:                                // 피크
                try {
                     x = s.peek();
                    System.out.println("피크한 데이터는 " + x + "입니다.");
                 } catch (IntStack.EmptyIntStackException e) {
                    System.out.println("스택이 비어있습니다.");
                }
                break;

             case 4:                                // 덤프
                s.dump();
                break;
            }
        }
    }
}
  1. LastNElements
// 원하는 개수만큼 값을 계속 입력받고, 요솟수가 N인 배열에 마지막 N개를 저장

import java.util.Scanner;

class LastNElements {
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        final int N = 10;
        int[] a = new int[N];    // 읽어 들인 값을 저장
        int cnt = 0;             // 읽어 들인 개수
        int retry;               // 다시 한 번?

        System.out.println("정수를 입력하세요.");

        do {
            System.out.printf("%d번째 정수: ", cnt + 1);
            a[cnt++ % N] = stdIn.nextInt();
          System.out.print("계속 할까요? (Yes…1／No…0) : ");
            retry = stdIn.nextInt();
        } while (retry == 1);

        int i = cnt - N;
        if (i < 0) i = 0;

        for ( ; i < cnt; i++)
            System.out.printf("%2d번째 ＝ %d\n", i + 1, a[i % N]);
    }
}
  1. IntStack
// int형 고정 길이 스택

public class IntStack {
    private int[] stk;           // 스택용 배열
    private int capacity;        // 스택의 크기
    private int ptr;             // 스택 포인터

    //--- 실행시 예외: 스택이 비어있음 ---//
    public class EmptyIntStackException extends RuntimeException {
        public EmptyIntStackException() { }
    }

    //--- 실행시 예외: 스택이 가득 참 ---//
    public class OverflowIntStackException extends RuntimeException {
        public OverflowIntStackException() { }
    }

    //--- 생성자(constructor) ---//
    public IntStack(int maxlen) {
        ptr = 0;
        capacity = maxlen;
        try {
            stk = new int[capacity];          // 스택 본체용 배열을 생성
        } catch (OutOfMemoryError e) {        // 생성할 수 없음
            capacity = 0;
        }
    }

    
    //--- 스택에 x를 푸시 ---//
    public int push(int x) throws OverflowIntStackException {
        if (ptr >= capacity)                                    // 스택이 가득 참
            throw new OverflowIntStackException();
        return stk[ptr++] = x;
    }

    //--- 스택에서 데이터를 팝(정상에 있는 데이터를 꺼냄) ---//
    public int pop() throws EmptyIntStackException {
        if (ptr <= 0)                                          // 스택이 빔
            throw new EmptyIntStackException();
        return stk[--ptr];
    }

    //--- 스택에서 데이터를 피크(peek, 정상에 있는 데이터를 들여다봄) ---//
    public int peek() throws EmptyIntStackException {
        if (ptr <= 0)                                        // 스택이 빔
            throw new EmptyIntStackException();
        return stk[ptr - 1];
    }

    //--- 스택을 비움 ---//
    public void clear() {
        ptr = 0;
    }
    //--- 스택에서 x를 찾아 인덱스(없으면 –1)를 반환 ---//
    public int indexOf(int x) {
        for (int i = ptr - 1; i >= 0; i--)     // 꼭대기 쪽부터 선형 검색
            if (stk[i] == x)
                return i;         // 검색 성공
        return -1;                // 검색 실패
    }

    //--- 스택의 크기를 반환 ---//
    public int getCapacity() {
        return capacity;
    }

    //--- 스택에 쌓여있는 데이터 갯수를 반환 ---//
    public int size() {
        return ptr;
    }

    //--- 스택이 비어있는가? ---//
    public boolean isEmpty() {
        return ptr <= 0;
    }

    //--- 스택이 가득 찼는가? ---//
    public boolean isFull() {
        return ptr >= capacity;
    }

    //--- 스택 안의 모든 데이터를 바닥 → 정상 순서로 표시 ---//
    public void dump() {
        if (ptr <= 0)
            System.out.println("스택이 비어있습니다.");
        else {
            for (int i = 0; i < ptr; i++)
                System.out.print(stk[i] + " ");
            System.out.println();
        }
    }
}
  1. 예제
  • 로직만 짰을 때
import java.util.Scanner;

public class stack1 {
    public static void main(String[] args) {
        int n, i, data;
        // 명령 i, o, c
        String cmd;

        // 스택
        int[] stack = new int[100];
        int nIndex = 0;

        Scanner in = new Scanner(System.in);
        // 명령의 수
        n = Integer.parseInt(in.nextLine());

        for (i = 0; i < n; i++) {
            cmd = in.nextLine();

            // insert
            if ("i".equals(cmd.substring(0, 1))) {
                data = Integer.parseInt(cmd.substring(2));
                stack[nIndex++] = data;
            }
            // out
            else if ("o".equals(cmd)) {
                if (nIndex == 0) {
                    System.out.println("empty");
                } else {
                    System.out.println(stack[--nIndex]);
                }
            }
            // count
            else if ("c".equals(cmd)) {
                System.out.println(nIndex);
            }
        }
    }
}
  1. 자바식으로
import java.util.Scanner;

public class stack2 {
    private static int count() {
        return nIndex;
    }

    private static void push(int data) {
        stack[nIndex++] = data;
    }

    private static int pop() {
        return stack[--nIndex];
    }

    private static boolean isEmpty() {
        return nIndex == 0;
    }

    static int nIndex = 0; // 스택의 인덱스
    static int[] stack = new int[100]; // 스택 배열

    public static void main(String[] args) {
        int n, i, data;
        String cmd;

        Scanner in = new Scanner(System.in);
        n = Integer.parseInt(in.nextLine());

        for (i = 0; i < n; i++) {
            cmd = in.nextLine();

            if ("i".equals(cmd.substring(0, 1))) {
                data = Integer.parseInt(cmd.substring(2));
                push(data);
            } else if ("o".equals(cmd)) {
                if (isEmpty()) {
                    System.out.println("empty");
                } else {
                    System.out.println(pop());
                }
            } else if ("c".equals(cmd)) {
                int num = count();
                System.out.println(num);
            }
        }
    }

}

🍐 큐

  1. Queue(큐)
import java.util.Scanner;

public class que {

    private static Scanner in;

    public static void main(String[] args){
        in = new Scanner(System.in);
        //queue

        int queue[] = new int[100];
        // 뒤
        int rear = 0;
        // 아ㅠ
        int front = 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])){
                queue[rear++] = Integer.parseInt(cmd.substring(2));
            }
            //out
            else if("o".equals(cmd)){
                if(queue[front]==0) System.out.println("empty");
                else System.out.println(queue[front++]);
            }
            //count
            else if("c".equals(cmd)){
                System.out.println(rear-front);
            }
        }
    }
}
  1. IntQueue
// int형 고정 길이 큐

public class IntQueue {
    private int[] que;            // 큐용 배열
    private int capacity;         // 큐의 크기
    private int front;            // 맨 처음 요소 커서
    private int rear;             // 맨 끝 요소 커서
    private int num;              // 현재 데이터 개수

    //--- 실행시 예외: 큐가 비어있음 ---//
    public class EmptyIntQueueException extends RuntimeException {
        public EmptyIntQueueException() { }
    }

    //--- 실행시 예외: 큐가 가득 찼음 ---//
    public class OverflowIntQueueException extends RuntimeException {
        public OverflowIntQueueException() { }
    }

    //--- 생성자(constructor) ---//
    public IntQueue(int maxlen) {
        num = front = rear = 0;
        capacity = maxlen;
        try {
            que = new int[capacity];          // 큐 본체용 배열을 생성
        } catch (OutOfMemoryError e) {        // 생성할 수 없음
            capacity = 0;
        }
    }

    
    //--- 큐에 데이터를 인큐 ---//
    public int enque(int x) throws OverflowIntQueueException {
        if (num >= capacity)
            throw new OverflowIntQueueException();            // 큐가 가득 찼음
        que[rear++] = x;
        num++;
        if (rear == capacity)
            rear = 0;
        return x;
    }

    //--- 큐에서 데이터를 디큐 ---//
    public int deque() throws EmptyIntQueueException {
        if (num <= 0)
            throw new EmptyIntQueueException();            // 큐가 비어있음
        int x = que[front++];
        num--;
        if (front == capacity)
            front = 0;
        return x;
    }

    //--- 큐에서 데이터를 피크(프런트 데이터를 들여다봄) ---//
    public int peek() throws EmptyIntQueueException {
        if (num <= 0)
            throw new EmptyIntQueueException();            // 큐가 비어있음
        return que[front];
    }

    //--- 큐를 비움 ---//
    public void clear() {
        num = front = rear = 0;
    }

    //--- 큐에서 x를 검색하여 인덱스(찾지 못하면 –1)를 반환 ---//
    public int indexOf(int x) {
        for (int i = 0; i < num; i++) {
            int idx = (i + front) % capacity;
            if (que[idx] == x)                // 검색 성공
                return idx;
        }
        return -1;                            // 검색 실패
    }

    //--- 큐의 크기를 반환 ---//
    public int getCapacity() {
        return capacity;
    }

    //--- 큐에 쌓여 있는 데이터 개수를 반환 ---//
    public int size() {
        return num;
    }

    //--- 큐가 비어있는가? ---//
    public boolean isEmpty() {
        return num <= 0;
    }

    //--- 큐가 가득 찼는가? ---//
    public boolean isFull() {
        return num >= capacity;
    }

    //--- 큐 안의 모든 데이터를 프런트 → 리어 순으로 출력 ---//
    public void dump() {
        if (num <= 0)
            System.out.println("큐가 비어있습니다.");
        else {
            for (int i = 0; i < num; i++)
                System.out.print(que[(i + front) % capacity] + " ");
            System.out.println();
        }
    }
}
  1. IntQueueTest
// int형 고정 길이 큐의 사용 예

import java.util.Scanner;

class IntQueueTester {
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        IntQueue s = new IntQueue(64);    // 최대 64개를 인큐할 수 있는 큐

        while (true) {
        	System.out.println(" "); // 메뉴 구분을 위한 빈 행 추가
            System.out.printf("현재 데이터 개수: %d / %d\n", s.size(), s.getCapacity());
            System.out.print("(1)인큐　(2)디큐　(3)피크　(4)덤프　(0)종료: ");

            int menu = stdIn.nextInt();
            if (menu == 0) break;

            int x;
            switch (menu) {
             case 1:                                // 인큐
                System.out.print("데이터: ");
                x = stdIn.nextInt();
                try {
                    s.enque(x);
                 } catch (IntQueue.OverflowIntQueueException e) {
                    System.out.println("큐가 가득 찼습니다.");
                }
                break;

             case 2:                                // 디큐
                try {
                     x = s.deque();
                    System.out.println("디큐한 데이터는 " + x + "입니다.");
                 } catch (IntQueue.EmptyIntQueueException e) {
                    System.out.println("큐가 비어 있습니다.");
                }
                break;

             case 3:                                // 피크
                try {
                     x = s.peek();
                    System.out.println("피크한 데이터는 " + x + "입니다.");
                 } catch (IntQueue.EmptyIntQueueException e) {
                    System.out.println("큐가 비어 있습니다.");
                }
                break;

             case 4:                                // 덤프
                s.dump();
                break;
            }
        }
    }
}

🍐 리스트

💫 추가 공부할 것 1. Comparator 인터페이스 학습 2. *`Iterator 인터페이스 학습`*

1. 관련 정리한 내 블로그

  • 수업 내용을 기반으로 좀 더 추가 함

Array-vs-ArrayList-vs-LinkedList-차이

연결리스트

2. 배열의 삭제

// 배열
        Number[] numbers = {10, 20, 30, 40, 50};
        System.out.println(Arrays.toString(numbers));

        // 30값을 삭제, 배열은 따로 삭제 메서드가 없어서 null 추가
        numbers[2] = null;
        System.out.println(Arrays.toString(numbers));

3. ArrayList의 할당

// 크기를 따로 지정하지 않음
        List<Number> list1 = new ArrayList<Number>(); //동적할당
        list1.add(10);
        list1.add(20);
        list1.add(30);
        list1.add(40);
        list1.add(50);
        System.out.println(list1.size()); //list의 크기값 반환, list에 담긴 요소의 개수

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

        list1.addAll(list2); //list1에 list2 추가
        System.out.println(list1.size());
        System.out.println(list1);

4. ArrayList의 값 추가

//list2에 80 삽입(index, data)
        list2.add(80);
        System.out.println(list2);
        // 기존 자료는 뒤로 밀려나고 삭제되지 않는다.
        list2.add(0, 100);
        System.out.println(list2);

        // 뒤로 밀어내는 동작을 하기 때문에 사이즈가 커질수록 비효율적

        //list2.add(50, 200); //논리적인 공간을 넘어 접근하는 경우 발생

5. 요소 삭제

// 요소 삭제 : remove()
        list2.remove(2);
        System.out.println(list2);

6. 요소 완전히 삭제

// clear() : 요소 완전히 삭제
        list2.clear();
        System.out.println(list2);

7. 요소 얻어내기

// 요소 얻어내기 : Object get(index), List subList(int frontIndex,int totalIndex)
        Number n = list1.get(0);
        System.out.println(n);

        //list1에서 40값을 출력
        n = list1.get(3);
        System.out.println(n);

        System.out.println(list1.subList(0, 5)); // 40까지 출력
        System.out.println(list1.subList(3, 5)); // 40,50
        System.out.println(list1.subList(2, 6)); // 30,40, 50, 60

8. 요소 변경

//요소 변경(update) : Object set(index, Object) 해당 인덱스의 데이터를 변경하여서 인덱스 변화 없으
        list1.set(0, 500);
        System.out.println(list1);

9. 생성

// 정수형 객체만 저장 가능한 ArrayList numbers1을 생성
        ArrayList<Integer> numbers1 = new ArrayList<Integer>();
        // 초기 용량(capacity) 지정 ArrayList numbers2 생성
        ArrayList<Integer> number2 = new ArrayList<Integer>();
        // 배열을 넣어 생성 ArrayList numbers3 생성 => 배열을 만든 것과 같음
        ArrayList<Integer> number3 = new ArrayList<Integer>(Arrays.asList(10, 20, 30));
        // 다른 컬렉션으로부터 그대로 요소를 받아와 생성 ArrayList numbers4 생성
        ArrayList<Integer> number4 = new ArrayList<Integer>(number3);

10. arrayList의 용량 운영 기능

//arrayList의 용량 운영 기능 : int size(), void ensureCapacity(최소값 지정), void trimToSize()

        List<Number> list3 = new ArrayList<Number>(5); //용량 10을 설정 => 오버헤드를 줄일 수 있음

        list3.add(1);
        list3.add(2);
        list3.add(3);
        list3.add(4);
        list3.add(5);
        list3.add(6);
        list3.add(7);
        System.out.println(list3.size()); // 크기 7

        List<Number> list4 = new ArrayList<Number>(5);
        list4.add(1);
        list4.add(2);
        list4.add(3);
        list4.add(4);
        list4.add(5);

11. list4 복사 하기 Object clone() : ArrayList 복제

// Object에서 상속받은 clone 메소드
        Object clonelist4 = ((ArrayList<Number>)list4).clone();
        ArrayList list4_1 = (ArrayList) clonelist4;
        System.out.println(list4_1.toString());

12. 정렬

// 정렬 : void sort(Comparator c) 지정된 정렬기준으로 ArrayList 정렬(원본 리스트 자동)

        List list5 = new ArrayList(5);
        list5.add("3");
        list5.add("2");
        list5.add("1");
        list5.add("4");
        list5.add("5");

        //오름차순 정렬
        list5.sort(Comparator.naturalOrder());
        System.out.println(list5.toString());
        //내림차순 정렬
        list5.sort(Comparator.reverseOrder());
        System.out.println(list5); //Comparator 인터페이스 학습

13. ArrayList 순회

// ArrayList 순회 : Iterator 인터페이스 활용
        Iterator<Integer> it = list5.iterator();
        while(it.hasNext()){
            System.out.println(it.next());
        }

🍐 ArrayList 예제

  • 이 코드는 MyArrayList 클래스를 통해 리스트를 구현하고, 이를 테스트하는 MyList_Main 클래스를 제공
  • 리스트 동작을 위한 add, remove, get, set 메서드는 일부 구현되어 있으며, ListIterator를 통해 리스트를 순회할 수 있도록 구현되어 있다.
  • 이를 통해 리스트의 동작 방식을 이해하고 활용할 수 있다.
  • 수정 해야 함… ⇒ 이해가 잘 안돼
  1. MyList
// ArrayList 클래스는 List인터페이스를 implements하여 구현한 클래스
// 직접 interface를 구현하고 추상메서드를 정의한 후 구현클래스에서 추상클래스를 구현해
// 봄으로써 ArrayList 코드 내부 동작원리 이해
public interface Mylist<T> {
    boolean add(T value); //요소 추가

    void add(int index, T value); //요소를 특정 위치에 추가

    boolean remove(Object value); //요소를 삭제
    T remove(int index); //특정 위치 요소 삭제

    T get(int index); //위치의 요소를 가져오기
    void set(int index, T value); //특정 위치에 있는 요소를 새 요소로 대체

    boolean contains(Object value); // 특정 요소가 리스트에 있는지 여부를 확인

    int indexOf(Object value); // 특정 요소가 몇 번째 위치에 있는지를 반환 (순차 검색)

    int lastIndexOf(Object o); // 특정 요소가 몇 번째 위치에 있는지를 반환 (역순 검색)

    int size(); // 요소의 개수를 반환

    boolean isEmpty(); // 요소가 비어있는지

    public void clear(); // 요소를 모두 삭제
}
  1. MyListIterator
public interface MyListIterator<T>{
    T next(); // next 메세드로 다음 요소 반환
    boolean hasNext(); // hasNext로 다음 요소의 존재 여부 확인 가능
    T previous();
    boolean hasPrevios();
    void add(Object element);
    void remove();
}
  1. MyArrayList
import java.util.Arrays;

public class MyArrayList<E> implements Mylist<E> {

    // 기본 용량 및 빈 배열 정의
    private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] EMPTY_ELEMENTDATA = {};

    // 배열의 총 개수(크기)와 데이터를 담을 배열 선언
    private int size;
    Object[] elementData;

    // 기본 생성자: 용량을 기본값으로 초기화하고 크기를 0으로 설정
    public MyArrayList() {
        this.elementData = new Object[DEFAULT_CAPACITY];
        this.size = 0;
    }

    // 용량을 직접 설정하는 생성자
    public MyArrayList(int capacity) {
        if (capacity > 0) {
            this.elementData = new Object[capacity];
        } else if (capacity == 0) {
            this.elementData = new Object[DEFAULT_CAPACITY];
        } else if (capacity < 0) {
            // 음수 용량은 예외 처리
            throw new RuntimeException(new IllegalAccessError("리스트 용량을 잘못 설정 : 음수값을 허용하지 않습니다."));
        }
        this.size = 0; // 초기 크기를 0으로 설정
    }

    // resize() : 리스트에 요소를 추가/삭제 동작할 떄 index가 기본적으로 조정되어야한다.
    // 이를 위해 배열의 크기와 배열의 용량을 비교하여, 크기가 작은 경우 리사이징 처리하여 메모리를 최적화
    public void resize(){
        int element_capacity = elementData.length;
        //용량이 꽉 찬 경우
        if(element_capacity == size){
            int new_capacity = element_capacity * 2;
            elementData = Arrays.copyOf(elementData, new_capacity);
            return;
        }
        // 용량에 비해 데이터양이 적은 경우
        if((element_capacity/2)> size){
            int half_capacity = element_capacity;
            elementData = Arrays.copyOf(elementData, Math.max(half_capacity, DEFAULT_CAPACITY));
        }

        // 들어 있는 데이터가 없는 경우(빈 배열)
        if(Arrays.equals(elementData, EMPTY_ELEMENTDATA)){
            elementData = new Object[DEFAULT_CAPACITY]; //기본용량으로 초기화
        }
    }

    @Override
    public boolean add(E value) {
        elementData[size] = value;
        size++;

        return true;
    }

    @Override
    public void add(int index, E value) {
        //인덱스가 음수이거나 배열 크기가(size)를 벗어난 경우 예외발생
        if(index <0 || index > size){
            throw new IndexOutOfBoundsException();
        }
    }

    @Override
    public boolean remove(Object value) {
        return false;
    }

    @Override
    public E remove(int index) {
        return null;
    }

    @Override
    public E get(int index) {
        return null;
    }

    @Override
    public void set(int index, E value) {

    }

    @Override
    public String toString() {
        return Arrays.toString(elementData);
    }

    class ListIterator implements MyListIterator<E>{

        private int nextIndex = 0; //커서 위치

        @Override
        public E next() {
            return (E) elementData[nextIndex++];
        }

        @Override
        public boolean hasNext() {
            return nextIndex < elementData.length;
        }
    }
    public ListIterator listIterator(){
        return new ListIterator();
    }
}
  1. MyList_Main
public class MyList_Main {
    public static void main(String[] args){
        MyArrayList<Number> list = new MyArrayList<Number>(); //초기 용량이 10
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        System.out.println(list.toString());
        //list 이터레이터 반환
        MyListIterator<Number> listit = list.listIterator();

        while(listit.hasNext()){
            System.out.println(listit.next());
        }
    }
}

🍐 연결리스트 : LinkedList

  • 노드(객체)끼리 주소 포인터를 서로 가리키면서 링크(참조)하여 이어지는 구조
  • 리사이징 안됨
  • 데이터의 중간 삽입, 삭제 빈번할 경우 빠른 성능 제공
  • 하지만 임의의 요소에 대한 접근에 대한 성능은 좋지 못하다.
  1. Node
public class Node<T> {
    Node prev; //이전 노드 주소를 저장하는 필드 doubly linked list
    Node next; //다음 노드 주소를 저장하는 필드 singly linked list
    int data; //데이터를 저장하는 필드
}
  1. LinkedListEx
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;

public class LinkedListEx {
    public static void main(String[] args){
        //라이브러리에서 제공하는 생성자를 이용하여
        LinkedList<Integer> list = new LinkedList<Integer>();
        LinkedList<Integer> list2 = new LinkedList<Integer>(Arrays.asList(1, 2));

        //문자열 "J" "A" "V" "A" 배열을 할당하여 list3 생성
        LinkedList<String> list3 = new LinkedList<String>(Arrays.asList("J", "A", "V", "A"));

        // addFirst(object) : ArrayList와 다르게 맨 앞에 데이터 추가 가능
        // addLast(object)
        //add(object), add(inedx, object), addAll(Collection c)
        System.out.println(list3); //[J, A, V, A]
        list3.addFirst("Perfect");
        list3.addLast("Programming");
        System.out.println(list3); //[Perfect, J, A, V, A, Programming]
        list3.add("Backend14"); // [Perfect, J, A, V, A, Programming, Backend14]

        // 순회해서 가지고 옴
        Iterator<String> it = list3.iterator();
        while (it.hasNext()){
            System.out.print(it.next() + " "); //Perfect J A V A Programming Backend14
        }

        list3.removeFirst();
        System.out.println(list3); //[J, A, V, A, Programming, Backend14]

        list3.removeLast();
        System.out.println(list3); //[J, A, V, A, Programming]
    }
}

LinkedList 동작 원리 구현 코드

  1. MySingleLinkedList
package Linkedlist;

import java.util.Objects;

//import Linkedlist.Node;

public class MySingleLinkedList<E> {
    private Node<E> head; // 노드의 첫 부분을 가리키는 포인트
    private Node<E> tail; // 노드의 마지막 부분을 가리키는 포인트

    private int size; // 요소 갯수

    public MySingleLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    // inner static class
    private static class Node<E> {
        private E item; // Node에 담을 데이터
        private Node<E> next; // 다음 Node 객체를 가르키는 래퍼런스

        // 생성자
        Node(E item, Node<E> next) {
            this.item = item;
            this.next = next;
        }
    }

    private Node<E> search(int index) {
        // head(처음 위치) 서부터 차례로 index 까지 검색
        Node<E> n = head;
        for (int i = 0; i < index; i++) {
            n = n.next; // next 필드의 값(다음 노드 주소)를 재대입하면서 순차적으로 요소를 탐색
        }

        return n;
    }

    public void addFirst(E value) {

        // 1. 먼저 가장 앞의 요소를 가져옴
        Node<E> first = head;

        // 2. 새 노드 생성 (이때 데이터와 next 포인트를 준다)
        Node<E> newNode = new Node<>(value, first);

        // 3. 요소가 추가되었으니 size를 늘린다
        size++;

        // 4. 맨앞에 요소가 추가되었으니 head를 업데이트한다
        head = newNode;

        // 5. 만일 최초로 요소가 add 된 것이면 head와 tail이 가리키는 요소는 같게 된다.
        if (first == null) {
            tail = newNode;
        }
    }

    public void addLast(E value) {

        // 1. 먼저 가장 뒤의 요소를 가져옴
        Node<E> last = tail;

        // 2. 새 노드 생성 (맨 마지막 요소 추가니까 next 는 null이다)
        Node<E> newNode = new Node<>(value, null);

        // 3. 요소가 추가되었으니 size를 늘린다
        size++;

        // 4. 맨뒤에 요소가 추가되었으니 tail를 업데이트한다
        tail = newNode;

        if (last == null) {
            // 5. 만일 최초로 요소가 add 된 것이면 head와 tail이 가리키는 요소는 같게 된다.
            head = newNode;
        } else {
            // 6. 최초 추가가 아니라면 last 변수(추가 되기 전 마지막이었던 요소)에서 추가된 새 노드를 가리키도록 업데이트
            last.next = newNode;
        }
    }

    public void add(int index, E value) {

        // 1. 인덱스가 0보다 작거나 size 보다 같거나 클 경우 에러
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }

        // 2. 추가하려는 index가 0이면 addFirst 호출
        if (index == 0) {
            addFirst(value);
            return;
        }

        // 3. 추가하려는 index가 size - 1와 같으면 addLast 호출
        if (index == size - 1) {
            addLast(value);
            return;
        }

        // 4. 추가하려는 위치의 이전 노드 얻기
        Node<E> prev_node = search(index - 1);

        // 5. 추가하려는 위치의 다음 노드 얻기
        Node<E> next_node = prev_node.next;

        // 6. 새 노드 생성 (바로 다음 노드와 연결)
        Node<E> newNode = new Node<>(value, next_node);

        // 7. size 증가
        size++;

        // 8. 이전 노드를 새 노드와 연결
        prev_node.next = newNode;
    }

    public boolean add(E value) {
        addLast(value);
        return true;
    }

    @Override
    public String toString() {
        if (head == null) {
            return "[]";
        }

        Node<E> n = head;
        String result = "[";

        while (n.next != null) {
            result += n.item + ", ";
            n = n.next;
        }

        // n이 마지막일 경우 n.next가 null이니 루프문을 빠져나오게 되서 마지막 노드 삽입 처리를 해주어야 한다.
        result += n.item + "]";

        return result;
    }

    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }

        return search(index).item;
    }

    public void set(int index, E value) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }

        // 1. search 메소드를 이용해 교체할 노드를 얻는다.
        Node<E> replace_node = search(index);

        // 2. 교체할 노드의 요소를 변경한다.
        replace_node.item = null;
        replace_node.item = value;
    }

    public E removeFirst() {

        // 1. 만약 삭제할 요소가 아무것도 없으면 에러
        if (head == null) {
            throw new RuntimeException();
        }

        // 2. 삭제될 첫번째 요소의 데이터를 백업
        E returnValue = head.item;

        // 3. 두번째 노드를 임시 저장
        Node<E> first = head.next;

        // 4. 첫번째 노드의 내부 요소를 모두 삭제
        head.next = null;
        head.item = null;

        // 5. head가 다음 노드를 가리키도록 업데이트
        head = first;

        // 6. 요소가 삭제 되었으니 크기 감소
        size--;

        // 7. 만일 리스트의 유일한 값을 삭제해서 빈 리스트가 될 경우, tail도 null 처리
        if (head == null) {
            tail = null;
        }

        // 8. 마지막으로 삭제된 요소를 반환
        return returnValue;
    }

    public E remove() {
        return removeFirst();
    }

    public E remove(int index) {

        // 1. 인덱스가 0보다 작거나 size 보다 크거나 같은 경우 에러 (size와 같을 경우 빈 공간을 가리키는 거니까)
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }

        // 2. 인덱스가 0이면 removeFirst 메서드 실행하고 리턴
        if (index == 0) {
            return removeFirst();
        }

        // 3. 삭제할 위치의 이전 노드 저장
        Node<E> prev_node = search(index - 1);

        // 4. 삭제할 위치의 노드 저장
        Node<E> del_node = prev_node.next;

        // 5. 삭제할 위치의 다음 노드 저장
        Node<E> next_node = del_node.next;

        // 6. 삭제될 첫번째 요소의 데이터를 백업
        E returnValue = del_node.item;

        // 7. 삭제 노드의 내부 요소를 모두 삭제
        del_node.next = null;
        del_node.item = null;

        // 8. 요소가 삭제 되었으니 크기 감소
        size--;

        // 9. 이전 노드가 다음 노드를 가리키도록 업데이트
        prev_node.next = next_node;

        // 10. 마지막으로 삭제된 요소를 반환
        return returnValue;
    }

    public boolean remove(Object value) {

        // 1. 만약 삭제할 요소가 아무것도 없으면 에러
        if (head == null) {
            throw new RuntimeException();
        }

        // 2. 이전 노드, 삭제 노드, 다음 노드를 저장할 변수 선언
        Node<E> prev_node = null;
        Node<E> del_node = null;
        Node<E> next_node = null;

        // 3. 루프 변수 선언
        Node<E> i = head;

        // 4. 노드의 next를 순회하면서 해당 값을 찾는다.
        while (i != null) {
            if (Objects.equals(i.item, value)) {
                // 노드의 값과 매개변수 값이 같으면 삭제 노드에 요소를 대입하고 break
                del_node = i;
                break;
            }

            // Singly Linked List에는 prev 정보가 없기 때문에 이전 노드에도 요소를 일일히 대입하여야 함
            prev_node = i;

            i = i.next;
        }

        // 5. 만일 찾은 요소가 없다면 리턴
        if (del_node == null) {
            return false;
        }

        // 6. 만약 삭제하려는 노드가 head라면, 첫번째 요소를 삭제하는 것이니 removeFirst()를 사용
        if (del_node == head) {
            removeFirst();
            return true;
        }

        // 7. 다음 노드에 삭제 노드 next의 요소를 대입
        next_node = del_node.next;

        // 8. 삭제 요소 데이터 모두 제거
        del_node.next = null;
        del_node.item = null;

        // 9. 요소가 삭제 되었으니 크기 감소
        size--;

        // 10. 이전 노드가 다음 노드를 참조하도록 업데이트
        prev_node.next = next_node;

        return true;
    }

    public E removeLast() {
        return remove(size - 1);
    }
}
  1. LinkedListMain
public class LinkedListMain
{

	public static void main(String[] args) {
	    MySingleLinkedList<Number> list = new MySingleLinkedList<>();

	    list.add(3);
	    list.add(6);
	    list.add(4);
	    list.add(3);
	    list.add(8);
	    list.add(10);
	    list.add(11);
	    System.out.println(list); // [3, 6, 4, 3, 8, 10, 11]

	    list.add(6, 100);
	    list.add(0, 101);
	    list.add(1, 102);
	    System.out.println(list); // [101, 102, 3, 6, 4, 3, 8, 10, 11, 100]

	    list.removeFirst();
	    list.removeFirst();
	    list.remove(1);
	    System.out.println(list); // [3, 4, 3, 8, 10, 11, 100]

	    list.remove(3);
	    list.remove(3);
	    System.out.println(list); // [4, 8, 10, 11, 100]

	    System.out.println(list.get(4)); // 100

	    list.set(4, 999);
	    System.out.println(list); // [4, 8, 10, 11, 999]
	}
}

회고

알고리즘은 너무 어려워... 내가 수학적 사고가 부족한가 근데 또 코드 풀이를 보면 어려워 보이지는 않는데 알고리즘 적 사고를 하는 게 어렵다... 자바보다는 코테를 준비할 거면 파이썬이 나은 것 같고 배열의 크기 부분이라던지에서도 확실히 너무 차이가 난다... 근데 스프링 공부할 거면 자바도 공부해야 하고 할 거 너무 많아 ㅠㅠㅠㅠ 힝

profile
GoldenDusk
내 지식을 기록하여, 다른 사람들과 공유하여 함께 발전하는 사람이 되고 싶다. gitbook에도 정리중 ~
이전 포스트

멀티캠퍼스 백엔드 과정 48일차[8월 11일] - 검색, 필터링 팀작업 프로젝트에 대한 고민

다음 포스트

멀티캠퍼스 백엔드 과정52일차[8월 18일] - 자료구조, 알고리즘 문자열, 재귀

0개의 댓글