devlog

위와 같은 원본 데이터에 4번째 데이터에(인덱스3) 새로운 데이터를 '추가' 한다고 해보자.

4번째 데이터인 40은 사라지고 새로운 데이터인 50이 덮어씌워졌다. 그럼 List는 어떨까?

List는 4번째 자리에 50을 추가하고, 기존의 40은 5번째로 밀리며 데이터가 유지되었다.

그럼 위의 원본 데이터에 대해서 삭제는 어떨까??

배열

리스트

배열은 기존에 있던 데이터를 삭제하고, 해당 인덱스자리는 공란으로 남겨야 한다. 이에따라 개발자는 배열의 빈공간이 있는지 없는지를 추가적으로 체크해야 하는 수고가 있다.

그에반해 리스트는 40을 삭제하며, 50이 40의 자리로 내려왔다. 이렇게 리스트는 빈공간 없이 데이터를 적제한다.

List의 기능

자료구조의 타입을 결정하는 것은 그 자료구조의 동작방법이다.

그렇다면 List는 어떤 동작을 가지고 있어야 할까?

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

ArrayList와 LinkedList의 차이점

LinkedList numbers = new LinkedList(); ArrayList numbers = nes ArrayList();

위의 두코드는 무엇이 다를까?? 이 두코드의 사용법은 거의 같으며, 실행결과도 같다.

그렇지만 내부적인 구현방법이 다르다. 결론적으로 말하면 인덱스를 이용해서 데이터를 가져오는것이 빈번하다면, ArrayList를, 추가와삭제가 빈번하다면 LinkedList를 쓰는것이 훨씬 효과적이다.

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

ArrayList

ArrayList는

배열을 이용

해서 리스트를 구현한 것을 의미한다. 인덱스를 이용하기 때문에 인덱스를 이용한 조회가 빠르지만, 추가/삭제 연산은 느리다는 단점이 있다.

데이터의 추가

ArrayList는 배열을 이용해 List를 구현하므로, 배열의 특성을 그대로 가지고 있다.

데이터를 리스트의 처음이나 중간에 저장에 하게되면, 이후의 데이터들이 모두 한칸씩 뒤로 밀려나야 한다.

데이터의 삭제

데이터의 삭제역시 마찬가지다. 빈자리가 생기면 빈자리를 채우기 위해 데이터들이 한칸씩 이동한다.

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

데이터 조회

ArrayList는 배열을 이용한 List이기 때문에, 인덱스를 이용한 데이터 조회에서 매우 빠른 성능을 보여줍니다.

ArrayList의 사용법

자바에서 제공하는 ArrayList의 사용법에 대해서 알아보자.

생성

import java.util.ArrayList; //util패키지에 존재하기 때문에, import를 해줘야한다.
ArrayList<Integer> numbers = new ArrayList<>();

추가

List에 엘리먼트를 추가할때는 add()메소드를 사용한다. add메소드는 배열에 단순히 더하는 것이기 때문에, 빠르게 동작한다.

numbers.add(10); numbers.add(20); numbers.add(30); numbers.add(40); numbers.add(50);

위처럼 순서대로 추가되는 것이 아닌, 특정위치에 저장하고 싶다면 아래와 같은 메소드를 사용한다.

numbers.add(1,50);

여기서 ArrayList는 배열을 이용해서 List를 구현하다고 했다. 그런데 배열은 길이가 정해져있고, 그 길이를 넘어서는 갯수의 요소는 추가가 불가능하다. 그러나 List에서는 길이를 선언하지도, 또 길이에 따른 제한도 없다. 왜 일까??

ArrayList의 내부구현을 보면, add()연산중 배열의 길이를 넘게되면, 기존 배열크기의 2배의 새로운 배열을 생성하고, 기존배열을 신규배열에 복사한후, 신규배열을 반환한다. 그리고 이후 추가하려던 요소를 신규생성한 배열에 추가하게된다. 이렇게

배열의 크기를 키우는 과정에서 과부하

가 발생하게 된다.

삭제

특정 인덱스에 위치하는 요소를 삭제할 때는 remove()메소드를 사용한다.

numbers.remove(2);

조회

요소를 조회할때는 get()메소드를 사용합니다. 이때 배열을 사용하기 때문에, 매우 빠른 성능을 보여줍니다.

numbers.get(2);

반복

자바에서 ArrayList를 탐색하는 방법으로 Iterator를 제공한다. 향상된 for문이나, for문으로도 구현은 가능하다. 그러나 평소 Iterator에 대해 잘 몰랐으므로, 사용법을 공부해보자.

Iterator<Integer> ie =  numbers.iterator();
        while(ie.hasNext()) {
            System.out.println(ie.next());
        }
//더 간단한 방법으로 향상된 for루프가 있겠다.
for(int value : numbers){
    System.out.println(value);
}

LinkedList

LinkedList는 ArrayList와는 다르게 요소와 요소간의 연결(link)를 통해서 리스트를 구현했다.

즉 LinkedList에서 말하는 '연결'이 무엇인가를 아는것이 핵심이다.

ArrayList와 LinkedList의 메모리 할당

아래의 그림과 같이 메모리를 한 건물에 비유해보자.

ArrayListArrayList는 '배열'을 이용하기 때문에, 메모리할당에 있어서도 실제 연속된 공간을 할당받고, 배열의 길이를 벗어나는 요소를 추가하기 위해서는 기존 공간의 2배가 되는 공간을 미리 선점하고, 추가를 해야한다.
LinkedList반면 LinkedList 사무실자체가 띄엄띄엄 떨어져 있기때문에, 직원들이 늘어도 전체공간을 늘릴 필요갑없다. 빈 사무실 아무데나 들어가서 입주하면 되기 때문이다. 단, 사무실을 찾는데에 있어 하나의 요소마다 방문해서, 찾아가야 합니다. 왜냐면 다음요소에 대한 정보는 이전 요소만이 알고있기 때문에, 원하는 요소를 찾기까지는 그 이전의 모든 요소를 다 방문해야 합니다.

https://opentutorials.org/module/1335/8821
이런점에 있어 LinkedLinst는 조회에서 느린반면, 수정/삭제시 더빠르고, 메모리를 낭비하지 않습니다.

연결

배열과는 다르게 서로의 위치가 흩어져 있기 때문에 서로 '연결'되 있어야 한다. 이런 리스트에서 요소들은 노드 혹은 버텍스 등으로 불린다. (같은 리스트내의 요소지만, 다르게 부를뿐이다.)

LinkedList의 구체적인 구조

리스트는 노드(엘리먼트)들의 연속적인 모임이다. 따라서 내부적으로 노드를 가지고 있어야 한다.

ArrayList의 경우 그 엘리먼트가 배열의 엘리먼트였다면, LinkedList는 배열 대신 다른 구조를 사용한다. 노드는 최소한 두가지 정보를 알고있어야 한다. 자기 자신의 값과, 다음노드의 위치이다.

이렇게 각각의 노드가 다음노드를 알고있기 때문에 List를 구성할 수 있는 것이다.

아래의 그림을 보고 이해해보자.

자바에서는 이런 노드를 구현하기위해 객체에 데이터필드와 다음노드를 가리키는 링크필드를 만든다. 보통 데이터필드는 value, 링크필드는 next라는 변수명을 많이 쓴다. value에는 노드의 값을, next에는 다음 노드의 참조값을 저장하게 된다.

Head

위의 그림을 보면 Head라는 것이 있다. 이는 LinkedList의 첫번째 노드를 가리키는 것으로, 건물의 출입문과도 같다.

LinkedList의 데이터 추가

시작 부분에 추가

Vertex tmp = new Vertex(input) //input값을 가진 신규노드를 생성한다.
tmp.next = head; //신규노드의 next값 즉, 다음노드 값을 head로, 기존의 첫번째 노드 참조값을 할당한다.
head = tmp; // head에 새로운 첫번째 노드인 tmp의 참조값을 할당한다.

위 코드를 그림으로 다시한번 보자. input의 값을 85로 보면 되겠다.

값이 85인 신규노드를 생성한다.

신규노드의 next값을 기존의 첫번째 노드인 head(15)의 참조값으로 할당한다.

새롭게 첫번째 노드가 된 85노드의 참조값을 head에게 할당한다.

중간에 추가

위 그림의 초기 LinkedList에서 인덱스2에 새로운 데이터를 추가하고자 하는 코드이다. (즉, 값이6인 노드의 다음노드의 값을 23에서 새로운 노드로 바꾸려는 것이다. )

/
Vertex temp1 = head //head를 참조해 첫번째 노드를 찾는다.
while (--k!=0) // k=2로 초기화된 상태이다.
  temp1 = temp1.next // 다음 노드의 참조값을 할당 받는다.
Vertex temp2 = temp1.next // 이전노드의 원래의 next값을 기억하기위해 임시로 해당값의 노드를 생성
Vertex newVertex = new Vertex(input) // 추가하고자 하는 신규노드를 생성
temp1.next = newVertex //이전 값의 노드의 next를 신규생성한 노드의 참조값으로 바꾼다.
newVertex.next = temp2 // 임시저장했던 다음노드 값을 신규생성한 노드값의 next변수에 할다한다.

head의 값으로 첫번째 노드를 찾는다.

원하는 위치의 노드 이전 노드까지 탐색을 실시한다.

코드에는 없지만, 탐색한 노드의 next의 인덱스가 원하던 인덱스(2)라면 멈춘다.

또한 이전노드의 next값을 신규생성한 노드의 next로 할당해줘야 하기때문에, 임시로 노드객체를 생성한다.

추가하고자 하는 신규노드를 생성한다.(90)

이전 노드의 next값을 신규생성한 노드의 참조값으로 할당한다.

신규생성한 노드의 next값을 임시생성한 노드의 참조값으로 할당한다.

새로운 노드가 추가되었다!

데이터 삭제

삭제는 '중간에서 추가' 과정과 비슷하기 때문에 코드로만 설명한다.

Vertex cur = head //head의 값으로 첫번째 노드를 찾는다.
while (--k!=0)
  cur = cur.next //다음 노드로 이동.
Vertex tobedeleted = cur.next //삭제할 노드를 찾았다면 임시 객체를 생성한다. 
cur.next = cur.next.next //이전노드의 next값을 삭제할 노드의 next값으로 할당한다.
delete tobedeleted // 임시로 생성한 객체를 삭제한다. -> 참조값이므로 삭제시 참조된 객체도 삭제된다.

Doubly Linked List (이중연결리스트)

doubly linked list의 핵심은 노드와 노드가 '서로'연결되었다는 점이다. 단순 연결리스트의 노드와는 다르게 next값 뿐만이 아니라 previeous값을 가지고 있다.

덕분에 노드의 탐색이 양방향으로 가능하다는것이 가장 큰 장점이다.

장점

인덱스 위치의 노드를 가져올 때와, 반복자를 이용해 탐색할때 들어난다.

인덱스의 데이터 조회

단순 연결리스트가 최악의 경우 노드 전체를 탐색했던 것에 비해 이중연결 리스트는 그 연산의 양이 반으로 줄었다. 탐색하고자 하는 인덱스가 리스트 길이의 반보다 적으몬 next, 크면 previoust를 사용해 탐색한다!

노드 탐색하기

이중 연결리스트는 앞뒤로 탐색이 가능하다.

상황에 따라 탐색의 방향이 바뀌어야 하는 경우라면 이중 연결 리스트를 사용하도록 하자!

단점

단순연결리스트와 달리 previous 값을 더 저장하는 만큼 메모리의 사용이 더 커진다는 단점이다.

또한 그에따른 구현이 조금더 복잡해진다는 단점도 존재한다. 하지만 장점이 크기 떄문에 현실에 사용되는 대부분의 연결리스트는 이중연결리스트이다.

노드의 추가

단순연결리스트와 거의 비슷하지만, 중요한 차이점은 양방향으로 연결한다는 점이다. 새로운 노드(25)를 기존의 노드(20,30) 사이에 추가하 법을 알아보자.

신규노드를 생성한다.