자바의 Linked list

프로그램에서 데이터를 사용할 때 기본타입을 주로 사용합니다. 하나씩 변수를 사용하기도 하지만 같은 타입의 변수가 여러개 필요한 경우에는 배열을 사용합니다. 배열은 매우 유용한 자료구조입니다. 여러개의 변수를 하나의 이름으로 사용할 수 있고 인덱스를 이용해서 값을 바로 접근할 수 있습니다. 하지만 이 배열에는 치명적인 단점이 몇가지 존재합니다.

1. 한번 선언하면 크기를 바꿀 수 없습니다.

2. 값을 삽입하거나 삭제하기 힘듭니다.

값을 삽입하려면 일단 크기가 가능한가를 확인해야하고 삽입할 자리이후의 모든 값을 뒤로 옮겨야합니다. 삭제의 경우는 값을 삭제하고 뒤에 있는 모든 값을 앞으로 옮겨야합니다. 크기가 작다면 별 상관이 없겠지만 크기가 크다면 굉장히 비효율적이 될 것이고 삽입과 삭제가 자주 일어난다면 굉장히 비효율적일 뿐 아니라 크기가 넘어가는 경우라면 새로 큰 배열을 정의하고 값을 모두 옮겨야하는 사태까지 벌어지게 됩니다. 이러한 문제들을 해결하기 위해 Linked list를 도입하게 되었습니다. Linked list는 여러개의 값을 저장한다는 점은 배열과 같지만 저장하는 방법이 다릅니다. 하나의 d엘리먼트는 값과 주소로 나뉘게 됩니다. 값은 배열에 저장된 값과 같습니다. 하지만 주소는 다음 값을 가지고 있는 엘리먼트의 주소값을 가집니다. 그래서 배열처럼 크기가 정해져있지않고 연속된 메모리를 차지하지 않습니다. 일단 작은 수의 데이터를 가진 배열과 Linked list를 비교해보겠습니다.

1

3

4

5

배열은 위와 같이 연속된 메모리에 값을 저장합니다. 그래서 인덱스를 이용해서 바로 값에 접근을 할 수 있습니다. 위의 배열은 5개의 정수값을 가진 배열입니다.

하지만 Linked list는 연속된 메모리에 값을 저장하지 않고 각각의 엘리먼트를 선언할 때마다 할당을 합니다.

위와 같이 4개의 엘리먼트가 존재하고 다음 엘리먼트의 주소값을 가지고 있어서 그림과 같이 다음 엘리먼트를 접근할 수 있도록 해줍니다. 위의 경우는 처음서부터 접근을 해야되기 때문에 배열처럼 바로 접근을 할 수는 없습니다. 하지만 삽입에는 무척 편하게 되어있습니다.

위의 2경우에 1뒤에 2를 삽입하려고 한다면 배열은 3, 4, 5를 모두 한칸씩 뒤로 옮기고 2번째에 값을 저장해야합니다. 이번 경우는 5개짜리 배열이기때문에 간단해 보이지만 크기가 엄청 크다면 굉장히 비효율적이 됩니다. 더군다나 삽입이 굉장히 자주 일어난다면 더 문제가 될 것입니다.

하지만 Linked list인 경우는 2를 가진 엘리먼트를 하나 생성하고 1을 가진 엘리먼트의 주소값을 2를 가진 엘리먼트의 주소로 변경하고 2를 가진 엘리먼트의 주소값을 3을 가진 엘리먼트의 주소로 저장하면 됩니다. 이 것은 크기가 얼마나 크던지 상관이 없습니다.

배열과 Linked list 중 어느 것이 낫다는 것이 아니라 필요에 의해 사용해야 한다는 것입니다. 프로그램에서 이용할 수 있는 굉장히 많은 자료구조들이 있습니다. 우리는 이것을 알아야 필요할때 가장 알맞은 자료구조를 사용할 수 있습니다. Linked list는 가장 원시적인 형태입니다. 자료값에 접근을 하려면 처음부터 하나씩 접근해야 하고 다시 전으로 돌아갈 수도 없습니다. 그래서 Double Linked list라는 것이 생겨났습니다. 이것은 하나의 엘리먼트가 이전 주소값, 값, 다음 주소 값의 3가지 요소를 가집니다. 그래서 다시 전으로 돌아갈 수 있게 됩니다. 이러한 자료구조는 초기에 만들어진 자료구조이고 이제는 프로그램언어에서 제공해주고 있습니다. 프로그래머가 프로그램에서 구현할 필요는 없다는 얘기입니다.

자바에는 ArrayList라는 것이 있습니다. 이것은 Linked list처럼 배열의 값을 증가할 수 있고 중간에 삽입과 삭제를 편하게 할 수 있습니다. 더군다나 인덱스를 이용해서 접근도 가능합니다. 한번 사용법을 살펴보도록 하겠습니다.

위의 소스에서 처럼 ArrayList는 크기를 정하지 않고서도 선언을 할 수 있습니다. 물론 크기를 정하고 선언할 수도 있습니다. ArrayList 클래스는 많은 메소드를 제공해 줍니다. add는 값을 저장하는 메소드입니다. 인수가 하나인 경우는 ArrayList의 마지막에 값을 저장합니다. 하지만 16번 라인같이 두개의 인수를 사용한다면 처음 값은 인덱스이고 두번째 값은 저장할 값입니다. 자바는 인덱스가 0부터 시작하므로 2번째 자리에 2를 넣으라는 얘기가 됩니다. 그래서 처음에 출력된 값은 [1, 3, 4, 5] 지만 두번째 출력된 값은 [1, 2, 3, 4, 5]입니다. 그리고 get메소드를 사용해서 해당 인덱스에 접근해서 값을 가져올 수 있습니다. 라인 20번에서 get(3)를 사용해서 3번인덱스의 값, 4번째 값인 4를 가져왔습니다. 이외에도 remove메소드를 제공해서 삭제를 할 수 있게 하는 등 여러가지 메소드를 제공합니다. ArrayList를 선언할 때 타입에 클래스 타입에 들어가야 합니다. 그래서 int가 아닌 Integer를 사용했습니다. 그래서 다른 타입도 마찬가지로 바꾸어주어야합니다. 실제 프로그램에서 간단한 경우에는 배열을 사용하지만 그렇지 않다면 많이 ArrayList를 사용합니다.