[JAVA] Array DataStructure & ArrayList와 LinkedList의 차이점

Data Structure (자료구조)

데이터를 효율적으로 저장하고 꺼내기 쉽게 만드는 것을 의미한다. 꺼내쓰기 쉽게 데이터를 잘 정리 정돈 하는 것이라고 할 수 있다. 이정도의 정의로 시작하여 차차 자료구조에 대해 공부하면서 바라보는 시야를 넓혀가자. 거의 모든 언어에 있는 배열은 대표적인 데이터 스트럭쳐라고 할 수 있다. 

배열 - Array

• 거의 모든 프로그래밍 언어에 포함되어 있다.
• 데이터를 하나의 변수에 그룹핑해서 관리하기 위한 방법
• 반복문과 결합하여 많은 정보를 효율적으로 처리
• 배열은 데이터 스트럭쳐이다.
• 매우 다양한 용도로 사용할 수 있는 데이터 스트럭쳐이다

ex)Array

//Array
String[] student = new String[5];
student[0] = "한진섭";
student[1] = "최찬호";
student[2] = "정화영";
student[3] = "김성국";
student[4] = "박용규";
student[1] = null;
for(int i=0; i<student.length; i++){
    System.out.println(student[i]); //  [한진섭, null, 정화영, 김성국, 박용규]
}
System.out.println("--");
for(int j=0; j<student.length; j++){
    if(student[j] != null){
        System.out.println(student[j]); // [한진섭, 정화영, 김성국, 박용규]
    }
}

배열의 한계

• 비어있는 데이터가 발생한다.
• 배열은 인덱스에 따라서 값을 유지하기 때문에 빈자리가 남게된다.
• 배열의 크기를 배열 생성 시 지정해아한다.
• 배열의 크기를 변경할 수 없다.

 

* 존재하지 않는 데이터는 아예 없애버리면?

즉, 삭제한 자리를 뒤에 위치한 엘리먼트로 메꾸는 것이다. 이렇게 데이터가 순서에 따라서 빈틈없이 연속적으로 위치하는 데이터 스트럭쳐를 List 라고 한다. 이렇게 되도 문제는 생긴다. 인덱스 1이 지워져 최찬호 학생이 없어지고 뒤에있는 학생들이 한칸 씩 앞으로 당겨지므로 뒤에 있는 학생들의 index 가 모두 바뀌게 된다. 인덱스로 학생을 찾는 프로그램이 있다면 이것은 문제가 발생하게 될 것이다

 

ex) ArrayList

// List
ArrayList<String> studentList = new ArrayList<String>();
studentList.add("한진섭");
studentList.add("최찬호");
studentList.add("정화영");
studentList.add("김성국");
studentList.add("박용규");
System.out.println("--");
System.out.println(studentList); // [한진섭, 최찬호, 정화영, 김성국, 박용규]
studentList.remove(1);
System.out.println(studentList); // [한진섭, 정화영, 김성국, 박용규]

* 배열의 활용

데이터의 크기가 확정적일 때 배열을 사용하면 메모리나 처리속도면에서 좋다. 또한 다른 데이터 스트럭쳐의 부품이 되기도 한다. 기능이 최소한이기 때문에 좋은 부품이  수 있다. 기능이 많을수록 사용하기에는 좋아도 용도가 제한되기 때문이다.

 

결론

• 배열은 거의 모든 언어에 포함된 데이터 스트럭쳐이다.
• 배열을 잘 다루는 것은 프로그래머의 기본적인 소양이다.
• 배열만으로 모든 상황을 만족시킬 수 없다.
• 이후 등장하는 대부분의 데이터 스트럭쳐들은 직간접적으로 배열을 품으로 사용다.
• 배열에 대한 이해는 모든 데이터 스트럭쳐 이해의 공통 요소이다. 

 

이번에는 Array 단점을 해결하였던 List DataStructure에 대해서 알아보도록하자

 

 

List

배열이 가지고 있는 인덱스라는 장점 버리는 대신 빈틈없는 데이터 적재라는 장점을 취한 데이터 스트럭쳐이다.

 

위에서 ArrayList를 사용해 중간의 데이터를 삭제하여 뒤에있는 데이터들이 자동으로 앞으로 당겨지는 것을 확인하였다.

 

이번에는 중간에 데이터를 추가해 보도록하자.

studentList.add(1,"안호영");

System.out.println(studentList); // [한진섭, 안호영, 정화영, 김성국, 박용규]

studentList.add(1,"안호영");
System.out.println(studentList); // [한진섭, 안호영, 정화영, 김성국, 박용규]

*리스트에서는 인덱스가 중요하지 않다. 리스트 데이터 스트럭쳐의 핵심은 엘리먼트들 간의 순서이다. 그래서 리스트를 다른 말로 시퀀스(Sequence)라고도 부른다. 즉, 순서가 있는 데이터의 모임이 리스트이다.

 

리스트의 기능

• 처음,끝, 중간에 엘리먼트를 추가/ 삭제하는 기능
• 리스트에 데이터가 있는지 체크하는 기능
• 리스트의 모든 데이터에 접근할 수 있는 기능

 

위에서 구현한 ArrayList를 LinkedList로 구분해도 동일하게 동작한다.

LinkedList<String> studentLiked = new LinkedList<String>();
studentLiked.add("한진섭");
studentLiked.add("최찬호");
studentLiked.add("정화영");
studentLiked.add("김성국");
studentLiked.add("박용규");
System.out.println("--");
System.out.println(studentLiked); // [한진섭, 최찬호, 정화영, 김성국, 박용규]
studentLiked.remove(1);
System.out.println(studentLiked); // [한진섭, 정화영, 김성국, 박용규]
studentLiked.add(1,"안호영");
System.out.println(studentLiked); // [한진섭, 안호영, 정화영, 김성국, 박용규]

 

ArrayList와 LinkedList의 차이

ArrayList arrayList = new ArrayList();

LinkedList linkedList = new LinkedList();

 

둘의 공통점은 둘다 List 라는 것이다.

둘은 사용법이 거의 같고 실행결과도 같다.

하지만 내부적인 구현방법이 다르다.

 

*자바는 왜 사용법도 비슷하고 실행결과도 같은 2가지를 제공할까?

인덱스를 사용하여 데이터를 가져오는 것이 빈번하다면 ArrayList가 빠르다. 하지만 데이터의 추가/삭제가 빈번하다면 LinkedList가 훨씬 효과적이다.

 

ArrayList

• 배열을 이용하여 리스트를 구현한 것
• 내부적으로 배열을 이용하기 때문에 인덱스로 접근하는 것이 빠르다.
• 데이터의 추가 / 삭제는 느리다.

 

데이터 추가

ArrayList는 내부적으로 데이터를 배열에 저장한다. 배열의 특성상 데이터를 리스트의 처음이나 중간에 저장하면 이후의 데이터들이 한 칸씩 뒤로 물러나야 한다.

 

데이터의 삭제

빈자리가 생기면 그 자리를 채우기위해 순차적으로 한칸씩 당겨야 한다.

 

데이터 가져오기

인덱스로 데이터를 가져올 때는 메모리 상의 주소를 정확하게 참조해서 가져오기 때문에 그 속도가 매우 빠르다.

 

*인덱스를 아파트에 비유하자면 각 방의 호수와 같다. 호수 즉, 인덱스만 정확히 알고 있다면 데이터를 가져오는 것은 매우 빠르다. 

 

 

LinkedList

• 엘리먼트와 엘리먼트 간의 연결(link)을 통해 리스트를 구현한 것이다.

 

*데이터 스트럭쳐를 배워야 하는 이유는 메모리의 효율적인 사용이라고 할 수 있다.

 

메모리의 구조 - 건물의 비유

ArrayList 건물

이 건물은 동일한 회사의 사무실은 한 곳에 모여있어야 한다는 규칙이 있다. 회사가 성장해서 사무실이 꽉 찾다면 더 많은 사람을 수용할 수 있는 공간으로 전체가 이동해야 한다.  하지만 방문자가 사무실을 찾아가는 법이 아주 쉽다. 한곳에 모여있고 호수(인덱스)가 정확히 고지되기 때문에 인덱스만 알고 있으면 쉽게 찾아 갈 수 있다.

 

LinkedList 건물

이 건물은 동일한 회사에서 필요에따라 어느 층이든 자유롭게 사무실을 추가할 수 있다. 다만 이렇게 되면 방문자가 사무실을 찾아가는 방법이 비 효율적이다. 사무실이 추가될 때 순서가 매겨지고 항상 첫번째 사무실에서 부터 순차적으로 찾아가면서 목적지에 도달하는 것이 LinkedList의 방식이기 때문이다. 따라서 LinkedList에서는 몇번째 엘리먼트를 찾아내는 것이 느리다.

비유는 비유일뿐 가볍게 생각하고 넘기자

 

연결

배열과 다르게 LinkedList는 위치가 흩어져 있기 때문에 서로 연결되어 있어야 한다. 그러한 점에서 연결된리스트 -> LinkedList라는 이름 갖게 된 것이다.

 

용어

LinkedList 에서는 연결된 엘리먼트들을 노드(node) 혹은 버텍스(vertex) 라고 부른다. 노드는 마디, 교점 / 버텍스는 정점, 꼭지점 이라는 의미를 가지고 있기 때문에 연결성이 강조된 표현이다.

 

구조

LinkedList는 노드들의 모임이다. 따라서 내부적으로 노드를 가지고 있어야 한다. 배열 대신에 다른 구조를 사용한다.

노드는 최소한 두가지 정보를 알고 있어야 한다. 노드의 값과 다음 노드의 정보이다. 각각의 노드가 다음 노드를 알고 있기 때문에 하나의 연결된 값의 모임을 만들 수 있는 것이다.

자바와 같은 객체지향 언어에서는 객체에 데이터 필드와 링크 필드를 생성한다. 데이터 필드는 value, 링크 필드는 next 로 이름을 지정하여 사용한다. value 에는 노드 값이 저장되고, next에는 다음 노드의 포인터나 참조값을 저장하여 노드와 노드를 연결한다.

 

Head

건물에 비유하자면 출입문에 해당한다. LinkedList 를 사용하기 위해서는 head가 가리키는 첫번째 노드를 찾아야 한다.

 

*ArrayList와 LinkedList의 핵심적인 차이

 

1. 추가/삭제

ArrayList의 경우 엘리먼트를 중간에서 추가/삭제 할 경우 해당 엘리먼트의 뒤에있는 모든 엘리먼트의 자리이동이 필요하기 때문에 추가/삭제가 느려진다.

LinkedList의 경우 추가/삭제 될 앨리먼트의 이전, 이후 노드의 참조값(next)만 변경하면 되기 때문에 속도가 빠르다. 

 

1. 데이터 조회

ArrayList는 인덱스를 이용하여 조회한다. 인덱스를 알고 있으면 해당 엘리먼트에 바로 접근 할 수 있기 때문에 매우 빠르다.

LinkedList는 head가 가리키는 노드부터 시작해서 순차적으로 노드를 찾아가는 과정을 거쳐야 한다. 찾고자 하는 엘리먼트가 가장 끝에 있다면 모든 노드를 탐색해야 하기 때문에 속도가 느려진다.

 

Trade off

트래이드 오프란 어떤 특성이 좋아지면 다른 특성이 나빠지는 상황을 의미한다. 데이터 스트럭쳐를 배워야 하는 이유중 하나는 이러한 트레이드 오프를 이해하기 위해서이다.  장점과 단점의 미묘한 균형을 이해할 수 있어야 올바른 선택을 할 수 있다.

정리 -

배열은 데이터를 그룹핑 하여 관리하기 위한 데이터 스트럭쳐이다. 배열에는 단점이 있는데 크기를 미리 지정해야 하기 때문에 크기를 변경할 수 없다는 것이다. 그러므로 데이터가 차든 안차든 지정해 놓은 크기만큼 메모리를 사용하고 있기 때문에 메모리 낭비가 될 수 있다. 또한 추가된 데이터의 각각의 요소에 접근하기가 어렵다. 반복문을 통해 각각의 요소를 직접 꺼내서 확인을 하면서 접근해야 한다는 단점이 있다. 

위의 단점을 보완한 것이 리스트 데이터 스트럭쳐이다. 리스트는 인덱스가 중요하지 않다. 오히려 각각의 데이터의 순서가 중요하다. 그렇기 때문에 중간에 데이터가 변경되면 뒤에있는 데이터들이 자동으로 앞으로  당겨지거나 뒤로 밀려지면서 인덱스를 업데이트하여 순서를 보장한다. 그 결과 데이터 크기를 미리 정하지않고 데이터가 변화될때마다 가변적으로 크기를 맞추기 때문에 메모리 활용에 있어서도 효율적이다.  

자바에서는 리스트에 배열의 기능을 섞어놓은 어레이리스트가 있다. 데이터를 배열에 저장하되 리스트의 데이터 스트럭쳐를 사용하여 인덱스를 자동으로 조절하여 순서를 보장한다. 각각의 데이터 요소에 인덱스가 정확히 명시되어 구분되어있기 때문에 인덱스만 알고있으면 해당 요소에 직접 접근이 가능하다. 데이터를 조회하는데 있어서 효율적이다. 하지만 데이터가 추가되고 삭제될때 속도가 느려질 수 있다. 예를들어 1부터 100까지의 데이터가 있는데 50번째에 데이터를 추가한다고 한다면 51~100까지의 데이터의 인덱스가 모두 1씩 뒤로 밀리는 작업을 진행해야한다. 끊임없이데이터가 추가되고 삭제되는 프로그래밍에서는 문제가 될 수 있다. 

위의 단점을 보완한 것이 링크드리스트이다. 이 리스트는 배열을 사용하지 않는다. 데이터가 변화할때  뒤에 있는 데이터들의 인덱스를 전부 변화하는 방식을 사용하지 않는다는 뜻이다. 링크드 리스트는 각각의 엘리먼트를 노드 혹은 버텍스로 구분짓고 해당 노드는 모두 다음노드의 참조값을 가지고 있다. 이 노드는 내부 구조에 따라 생성된 순서부터 시작하여 다음 노드의 참조값에 의해 열결되어진다. 위의 예처럼 1부터 100까지의 데이터에서 50번째에 데이터 x를 추가한다면 50번째 데이터를 찾아가서 50번째의 다음 노드 참조값을 x로 지정하고 x는 자신의 다음 노드 참조값을 51로만 지정하는 작업만 거치면 된다. 51~100까지의 데이터는 가만히 있어도 된다는 뜻이다. 이러한 특징은 링크드 리스트의 단점으로도 연결될 수 있는데 어레이리스트는 50을 찾아갈때 50의 인덱스로 다이렉트로 접근하지만 링크드리스트는 1부터 시작하여 노드 참조값을 타고 50까지 찾아가야 한다는 것이다. 

데이터를 조회하는 작업이 많은 경우 인덱스의 장점을 가진 ArrayList
데이터 추가/삭제 작업이 많은 경우 참조값만 변경하면 되는 LinkedList를 사용하자. 






참고

https://opentutorials.org/module/1335/8634

데이터 스트럭쳐란 무엇인가? - Data Structure (자료구조)

https://opentutorials.org/module/1335/8677
https://opentutorials.org/module/1335/8636

배열 - Data Structure (자료구조)