Array & Linked List

문지원(JiwonMoon)·2022년 6월 8일

CS array linked list

자료구조(DataStructure)

목록 보기

2/9

🤔 목적

컴퓨터공학의 기초가 되는 cs지식을 되새기면서 이 후 있을 기술면접을 대비를 하고자한다.

배열(Array) 란?

배열은 메모리 상에 데이터(원소)를 연속하게 배치한 자료 구조이다.
즉, 각각의 값(value)이 인덱스(index)를 부여하여 해당 데이터를 불러오는 자료구조이다.

배열은 대부분의 프로그래밍 언어에 포함되어 있을 정도로 프로그래밍에 많이 쓰이는 자료 구조이다.
또한 대부분의 자료구조는 배열에서 파생되어서 나온다.

특징

1. 메모리의 연속성

배열은 실제 메모리 상에도 메모리가 순차적으로 저장된다. 따라서 어느 위치에 있는지 인덱스로 손쉽게 접근할 수 있다.

인덱스를 통해 무작위 접근(random access)가 가능하여 검색 성능이 빠르다. 하지만 인덱스 사용은 연결리스트, 트리, 스택, 등 다른 자료구조들에 비해 삽입, 삭제가 어렵다

2. 자료형

배열은 선언될때 모든 칸에 있는 값들은 동일한 타입(Type)으로 선언된다.

3. 중복허용

배열은 값의 중복을 허용하는 자료형이다.

4. 확장불가

배열은 메모리 할당 시 더 이상 길이를 늘릴수 없다

이를 통해 할당된 메모리만 사용하므로 추가적인 메모리 사용이 없다 그렇기 때문에 처음 할당하면 이 후 크기를 바꿀수 없기 때문에 사용하지 않는 공간이라도 해당 메모리 공간을 차지하고 있어 메모리 낭비가 될 수 있다.

사용법

예시

//정수형 타입 배열 선언 & 고정변수
int[] arr = {1, 2, 3}; // 초기 선언

//정수형 타입 배열 선언 & 변수대입
int N = 10;
int[] arr = new int[N];
for(int i=0; i<N; i++){
	arr[i] = 1;
}

사용사례

데이터 개수가 확실하게 정해져 있고, 데이터 저장을 위한 자료구조일 때
삽입/삭제 작업이 적을 때
배열에 저장된 데이터를 검색하는 작업이 많을 때

Array VS ArrayList

배열(Array)를 학습하면서 Linked List와 관련된 점들을 많이 찾아 볼 수 있다.
또한 ArrayList VS LinkedList 구조를 이루어 ArrayList를 일반적인 배열로 취급하는 블로그들이 많다.
하지만 Array 와 ArrayList는 분명한 차이점이 존재한다.

일반 배열과 ArrayList는 인덱스로 객체를 관리한다는 점에서 동일하지만, 크기를 동적으로 늘릴 수 있다는 점에서 차이점이 있다.
ArrayList는 내부에서 처음 설정한 저장 용량(capacity)가 있다. 설정한 저장 용량 크기를 넘어서 더 많은 객체가 들어오게 되면, 배열 크기를 증가시킨다. 이 뿐만아니라 배열은 제네릭을 사용할 수 없지만, ArrayList는 타입 안정성을 보장해주는 제네릭을 사용할 수 있다.

연결리스트(Linked List) 란?

정의

연결리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.

특징

위 그림과 같이 데이터를 담고 있는 노드들이 연결되어 있는데 노드의 포인터가 다음이나 이전의 노드와 연결시켜준다. 또한 각 노드는 연속된 공간에 저장되어 있지 않고 메모리 여러 부분에 분포되어 있다 각 노드에 다음 노드의 주소를 저장함으로써 다음 노드를 탐색할 수 있다.

종류

1. 단일 연결 리스트

단일 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

2. 이중 연결 리스트

이중 연결 리스트의 구조는 단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고, 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

3. 원형 연결 리스트

원형 연결 리스트는 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

사용법

ArrayList

ArrayList arrList = new ArrayList();
        arrList.add("1");
        arrList.add("2");
        arrList.add("3");
        
// 출력 arrList.get();
// 삭제 arrList.remove();
// 크기 arrList.size();
// 검색 arrList.contains();

LinkedList

LinkedList<Integer> list = new LinkedList<Integer>();

// 추가 형태
list.addFirst(1);//가장 앞에 데이터 추가
list.addLast(2);//가장 뒤에 데이터 추가
list.add(3);//데이터 추가
list.add(1, 10);//index 1에 데이터 10 추가

// 삭제 형태
LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3,4,5));
list.removeFirst(); //가장 앞의 데이터 제거
list.removeLast(); //가장 뒤의 데이터 제거
list.remove(); //생략시 0번째 index제거
list.remove(1); //index 1 제거
list.clear(); //모든 값 제거

// 출력
LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3));

System.out.println(list.get(0));//0번째 index 출력
				
for(Integer i : list) { //for문을 통한 전체출력
    System.out.println(i);
}

Iterator<Integer> iter = list.iterator(); //Iterator 선언 
while(iter.hasNext()){//다음값이 있는지 체크
    System.out.println(iter.next()); //값 출력
}

// 크기
LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3));
System.out.println(list.size()); //list 크기 : 3

//검색
LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3));
System.out.println(list.contains(1)); //list에 1이 있는지 검색 : true
System.out.println(list.indexOf(1)); //1이 있는 index반환 없으면 -1

Array List vs Linked List

일단 ArrayList 는 위에서 언급했듯이 메모리를 할당할 때 크기를 지정하지않고 동적으로 값을 삽입하고 삭제할 수 있다.
그렇다면 또 LinkList랑은 뭐가 다른가?
List가 붙어서 혼동이 올 수 있지만, 분명 "Array" List 이다.
이 때문에 일반배열의 구조를 갖고 조건에서 차이가 생기는 것이다.
이 말은 특징적으로 Array 와 Linked List의 차이를 구분하는 셈이다.

구조적 차이 때문에 속도의 차이가 발생한다.
물론 순차적으로 추가/삭제 하는경우 비슷한 속도를 보이지만,

중간 데이터(비순차적)으로 추가/삭제할 경우 LinkedList가 ArrayList보다 빠르다.
그 이유는 중간 요소를 추가 또는 삭제하는 경우, LinkedList는 각 노드간 연결만 변경해주면 되기 때문에 처리속도가 빠르다.반면에 ArrayList는 각 요소들을 재배치하여 추가할 공간을 확보하거나 빈 공간을 채워야하기 때문에 처리속도가 늦다.