1. 배열

---

배열의 특징

• 많은 수의 데이터를 다룰 때 사용하는 자료구조

• 각 데이터를 인덱스와 1:1 대응 하도록 구성

• 데이터가 메모리 상에 연속적으로 저장

배열의 장점은 인덱스를 이용하여 데이터에 빠르게 접근이 가능합니다.

배열의 단점은 크기가 고정이 되어있다는 점입니다.

배열의 크기가 변경되거나 데이터 삭제시 번거롭습니다.

---

직접 구현해보기

배열의 초기화, 삽입, 제거를 해보겠습니다

class MyArray{
    int[] arr;

    // 배열의 초기 사이즈 설정 -> MyArray(int size)
    MyArray(int size){
        this.arr = new int[size];
    }

    // 배열의 데이터 삽입 -> public void insertData(int index, int data)
    public void insertData(int index, int data){
        if(index < 0 || index > this.arr.length){
            System.out.println("Index Error");
            return;
        }

        int[] arrDup = this.arr.clone();
        this.arr = new int[this.arr.length + 1];

        for(int i = 0; i < index; i++){
            this.arr[i] = arrDup[i - 1];
        }

        for(int i = index + 1; i < this.arr.length; i++){
            this.arr[i] = arrDup[i - 1];
        }

        this.arr[index] = data;
    }

    // 배열에서 특정 데이터 삭제 -> public void removeData(int data)
    public void removeData(int data){
        int targetIndex = -1;

        for(int i = 0; i < this.arr.length; i++){
            if(this.arr[i] == data){
                targetIndex = i;
                break;
            }
        }

        if(targetIndex == -1){
            System.out.println("해당 데이터가 배열에 존재하지 않습니다.");
        }else{
            int[]arrDup = this.arr.clone();
            this.arr = new int[this.arr.length - 1];
            
            for(int i = 0; i < targetIndex; i++)
                this.arr[i] = arrDup[i];
            
            for(int i = targetIndex; i < this.arr.length; i++){
                this.arr[i] = arrDup[i + 1];
            }
        }

    }

}

• 아래의 주석을 복사하여 직접 구현하면 복습이 가능합니다.

// 배열의 초기 사이즈 설정 -> MyArray(int size)

// 배열의 데이터 삽입 -> public void insertData(int index, int data)

// 배열에서 특정 데이터 삭제 -> public void removeData(int data)

---

2. 연결리스트

---

연결 리스트 (Linked List)란?

연결리스트의 특징

• 데이터를 링크로 연결해서 관리하는 자료구조
• 자료의 순서는 정해져 있지만, 배열과 달리 메모리상 연속성이 보장되지 않습니다.

연결리스트의 장점

• 데이터 공간을 미리 할당할 필요가 없습니다.
• 컴퓨터 메모리 입장에서 데이터 추가/삭제가 용이함니다.

연결리스트의 단점

• 연결구조를 위한 별도 데이터 공간이 필요합니다.
• 연결 정보를 찾는 시간이 필요합니다.

연결리스트 기본 구조

노드

노드는 연결리스트의 기본 데이터 저장 단위입니다.

노드는 값과 포인터로 구성이 됩니다.

• 값은 실질적인 값입니다.
• 포인터는 다음 노드나 이전 노드의 연결 정보를 갖습니다.
• 처음 노드를 head라고 부릅니다.
• 가장 끝 노드를 tail이라고 합니다.