🎇 Linked List
Linked List는 Array List와 다르게 엘리먼트와 엘리먼트 간의 연결(link)을 이용해서 리스트를 구현한 것을 의미한다. 그래서 이름도 Linked List이다.
Linked List에서 연결은 무엇일까? 또 연결이 아닌 것이 무엇인지 생각해보자.
🎞 메모리
먼저 컴퓨터의 동작 원리에 대해서 살펴보자. 컴퓨터에는 3가지 중요한 부품 CPU, 메모리, Storage가 있다. 메모리는 보통 RAM이라고 부른다. Storage는 HDD와 SSD같은 것들이 있다.
메모리는 속도가 매우 빠른 대신 용량이 작다.
그리고 전기를 끄면 데이터가 사라지는 속성을 가지고 있다.
반면에 스토리지는 매우 느리기 때문에 CPU와 함께 일을 하기에는 속도면에서 부족하다. 그래서 어떤 프로그램을 실행하면 그 프로그램과 데이터는 메모리로 옮겨진다.
그러므로 실행속도를 결정하는 것은 대체로 메모리이다. 우리가 Data Structure을 배우는 이유는 메모리의 효율적인 사용이라고 할 수 있다.
🎞 메모리의 구조
메모리를 건물에 비유해보자. 나의 회사가 한 건물의 일부를 임대해서 사용한다고 생각해보자.
Array List
배열은 건물을 이런 식으로 사용하는 것과 비슷하다. 회사가 더 성장한다고 해도 더 이상 새로운 직원을 뽑을 수 없다. 만약 더 많은 공간이 필요하다면 더 넓은 공간을 찾아서 전체가 이사해야 한다.
Linked List
Linked List는 한 건물 내에서 한 회사가 임대한 사무실이 서로 떨어져 있다. 덕분에 직원이 늘어도 걱정이 없다. 건물에서 비어있는 곳 아무 곳이나 들어가면 된다.
그런데 방문자가 사무실을 찾는 방법이 비효율적이다. 위의 그림에 있는 방문자가 3번째 사무실을 찾아가려면 화살표의 순서대로 움직여야 한다.
이런 방식이 Linked List이다. 그래서 몇 번째 엘리먼트를 찾는 것이 느리다.
반면에 Array List는 바로 엘리먼트를 찾을 수 있다. 매우 빠르다.
🔗 연결
Linked List는 배열과 다르게 위치가 흩어져 있기 때문에 서로 연결되어 있어야 한다. 그런 점에서 연결이라는 이름을 갖게 된 것이다.
Array List에서는 엘리먼트라는 이름을 사용했지만,
Linked List와 같이 연결된 엘리먼트들은
Node(노드, 마디, 교점의 의미)
Vertex(버텍스, 정점, 꼭지점의 의미)라고 부른다. 이 용어들은 연결성이 강조된 표현이라고 보면 된다.
🔗 구조
리스트는 노드(엘리먼트)들의 모임이다. 따라서 내부적으로 노드를 가지고 있어야 한다.
Array List의 경우 엘리먼트가 배열의 엘리먼트였다.
Linked List는 배열 대신에 다른 구조를 사용한다.
노드는 최소한 두 가지 정보를 알고 있어야 한다.
노드의 값, 다음 노드
각각의 노드가 다음 노드를 알고 있기 때문에, 하나의 연결된 값이 모임을 만들 수 있는 것이다.
이것을 구현하는 방법은 여러가지인데, Java와 같은 객체지향 언어라면 객체에 데이터 필드와 링크 필드를 만든다. 보통 데이터 필드는 value라는 이름의 변수, 링크 필드는 next변수를 사용한다.
value : 노드의 값
next : 다음 노드의 포인터 or 참조값
Head
Linked List를 사용하기 위해서는 이 head가 가리키는 첫 번째 노드를 찾아야 한다.
⚙ 데이터 추가
⚙ 시작 부분에 추가
노드를 첫 번째 위치에 추가해보자.
Node temp = new Node(input); // 새로운 노드 생성
temp.next = head; // 새로운 노드의 다음노드로 첫 번째 노드를 가리킨다. 
새로 만들어진 노드가 첫 번째 노드가 되도록 head의 값을 변경한다.
head = temp⚙ 중간에 추가
3번째 자리(index 2)에 90을 추가해보자.
Node temp1 = head; // head를 참조해서 첫 번째 노드를 찾는다. 3번째 자리에 새로운 노드를 위치시키기 위해서는, 2번째 자리를 알고 있어야 한다.
2번째 자리의 next로 새로운 노드를 지정해야하기 때문이다.
while(--k != 0) // 현재 k 값은 2
temp1 = temp1.next;2번째 자리의 next를 이용해서 3번째 자리를 찾아서 temp2로 지정한다.
Node temp2 = temp1.next;새로운 값의 새로운 노드를 생성한다.
Node newNode = new Node(input);2번째의 다음 노드로 새로운 노드를 지정한다.
temp1.next = newNode;새로운 노드의 다음 노드로 3번째 값을 지정한다.
newNode.next = temp2;
ArrayList와LinkedList의 핵심 차이
배열의 경우는 엘리먼트를 중간에 추가/삭제할 경우 해당 엘리먼트의 뒤에 있는 모든 엘리먼트의 자리 이동이 필요했다. 그래서 배열은 추가/삭제가 느리다.
반대로Linked List의 경우 추가/삭제가 될 엘리먼트의 이전, 이후 노드의 참조값(next)만 변경하면 되기 때문에 속도가 빠르다.
🐹 데이터의 제거
데이터를 제거하는 것도 추가하는 것과 비슷하다. 세번째 노드(index 2)를 제거하는 과정을 살펴보자.
우선 head를 이용하여 첫 번재 노드를 찾자.
Node current = head;두 번째 노드로 이동하자.
// k = 2
while (--k != 0)
current = current.next;세 번째 노드를 찾았다.
Node tobedeleted = current.next;두 번째 노드의 next를 23으로 변경하고, 90을 삭제해서 메모리에서 제거하자.
current.next = current.next.next;
delete tobedeleted;
⛹️♀️ index를 이용한 데이터 조회
index를 이용해서 데이터를 조회할 때, Linked List는 head가 가리키는 노드부터 시작해서, 순차적으로 노드를 찾아가는 과정을 거쳐야 한다.
만일 찾고자 하는 엘리먼트가 가장 끝에 있다면 모든 노드를 탐색해야 한다.
반면에 array를 이용해서 리스트를 구현하면 index를 이용해서 해당 엘리먼트에 바로 접근할 수 있기 때문에 매우 빠르다. trade off
trade off는 어떤 특성이 좋아지면 다른 특성이 나빠지는 상황을 의미한다. Array List와 Linked List가 trade off의 좋은 사례라고 할 수 있다.
우리가 data structure를 배우는 이유 중의 하나가 이러한 trade off를 이해하기 위해서이다. 장점과 단점의 미묘한 균형을 이해할 수 있어야 올바른 선택을 할 수 있다.
