TIL | Array와 Linked list의 차이

💪🏻 GOAL
Array와 Linked list의 차이를 이해하고,
Linked list를 활용한 기본 문제를 풀 수 있다.

Array / 배열

배열은 특정한 크기의 연속된 메모리 공간에 데이터를 저장하는 자료구조이다.
데이터들이 연속되어 저장되어 있기 때문에, 첫 데이터가 저장된 메모리 주소만 알면 자연적으로 다음 데이터의 위치를 알 수 있다. 예를 들어 세 번째 데이터의 위치를 알고자 한다면, 첫 번째 데이터의 주소(ex. 0x12)에서 두 개의 데이터 크기만큼 넘어가면 세 번째 데이터의 위치를 알 수 있다.

데이터 조회 시간복잡도 : O(1)
데이터 수정 시간복잡도 : O(n)

다만 데이터를 빈번하게 추가하거나 삭제할 경우,
변경하려고 하는 데이터 이후의 데이터의 위치를 모두 변경해야 하므로 효율적이지 못하다.

ex_ 길이 5의 배열에서 2번째를 삭제하는 경우, 3/4/5를 모두 한 칸씩 당겨야 한다
ex_ 길이 5의 배열에서 2번째를 추가하는 경우, 2/3/4/5를 모두 한 칸씩 밀어야 한다.

Linked List

Linked List는 말 그대로 요소와 요소간의 연결(link)를 이용해서 리스트를 구현한 자료구조이다.
Linked List의 데이터들은 메모리 공간에 연속적으로 존재하지 않으며, 이전 데이터가 다음 데이터의 위치를 저장하는 식으로 리스트를 형성한다. (자신을 기준으로 앞뒤 데이터의 주소를 기억!!)
그렇기 때문에 특정 데이터의 위치를 찾고 싶다면, 리스트 전체를 순차적으로 탐색해야 한다.

데이터 조회 시간복잡도 : O(n)
데이터 수정 시간복잡도 : O(1)

다만 배열과는 다르게 데이터를 추가하거나 삭제할 경우 시간복잡도 O(1)로 가능한데,
세 번째 위치에 데이터를 추가하고 싶다면, 두 번째 데이터가 다음 값을 가르키는 주소를 새로운 데이터의 주소로 변경하고 새로운 데이터의 다음 값을 가르키는 주소로 기존 세 번째 데이터(현재 네 번째 데이터)로 변경하면 되기 때문!

데이비드 호크니 전시를 보다가 Linked List의 구조를 발견함ㅋㅋㅋ

Linked List의 활용

❓ Question

You are given two non-empty linked lists representing two non-negative integers.
양수인 정수로 이루어진 두 개의 비어있지 않은 linked list가 주어집니다.

The digits are stored in reverse order, and each of their nodes contains a single digit.
숫자는 역순으로 저장되어 있으며, 각 노드는 하나의 자리수를 표현합니다.

Add the two numbers and return the sum as a linked list.
두 개의 숫자를 더하고 linked list의 합을 반환하세요.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.
두 개의 숫자는 모두 0으로 시작하지 않습니다 (ex. 012 / 005)

https://leetcode.com/problems/add-two-numbers/

✨ Answer

Linked list의 개념을 이해하긴 했지만, 실제로 문제에 적용하는 건 또다른 문제였다.
답으로 접근하는 방법을 알아내기 어려워 다른 사람들이 작성해놓은 solution들을 많이 찾아봤고, 그를 통해 이해한 과정을 작성해보려고 한다.

• ListNode 생성자를 통해 linked list의 노드가 구현되어 있다.
• 초기 ListNode를 생성한다. (val = 0 / next = null)
• 전달되는 linked list l1 & l2의 끝까지 반복문을 돈다.
  • 변수 sum에 첫 번째 l1의 노드를 더한다.
  • l1을 다음 노드로 옮긴다.
  • 변수 sum에 두 번째 l2의 노드를 더한다.
  • l2를 다음 노드로 옮긴다
  • 만약 l1 node + l2 node가 10 이상이면 다음 자릿수로 넘겨줄 수 있도록 carry 변수에 1을 더하고, sum 변수에서 10을 뺀 나머지를 저장한다.
  • head의 next로 구한 sum값의 ListNode를 생성한다. (자릿수 저장)
  • head를 다음 노드로 옮긴다.
  • carry에 저장해두었던 값을 넘겨주고 carry 변수를 초기화 한다.
• List.next를 반환한다.

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    var List = new ListNode(0);
    var head = List;
    var sum = 0;
    var carry = 0;

    while(l1!==null||l2!==null||sum>0){
        if(l1!==null){
            sum = sum + l1.val;
            l1 = l1.next;
        }
        if(l2!==null){
            sum = sum + l2.val;
            l2 = l2.next;
        }
        if(sum>=10){
            carry = 1;
            sum = sum - 10;
        }

        head.next = new ListNode(sum);
        head = head.next;

        sum = carry;
        carry = 0;

    }

    return List.next;
};

문제를 이해하면서 헷갈렸던 두 가지는 아래와 같다.

1. List와 head를 왜 따로 선언하여 사용할까?
   List와 head는 같은 linked list를 공유하지만 역할이 다르다고 볼 수 있는데,
   head는 linked list의 각 노드를 하나씩 가르키면서 값을 처리하는 데 사용되며
   List는 초기값으로 유지되어 마지막에 값을 반환하는데 사용된다.

2. 더한 값을 저장한 linked list의 모든 값을 반환해야 하는데 왜 List.next를 반환할까?
   이 부분을 검색하면서 아래 stackoverflow에서 답을 찾을 수 있었다.
   List.next는 해당 값의 value를 포함한 다음 모든 값에 대한 내용을 포함하고 있다는 것.
   말로 설명하면 이해가 어려운데 아래 예시를 보면 바로 이해가 될 것이다.
   https://stackoverflow.com/questions/56433243/why-is-head-next-printing-the-whole-linked-list

{
    "val" : 1,
    "next" : {
        "val" : 2,
        "next" : {
            "val" : 3,
            "next": null
        }
    }
}

Linked list를 활용한 알고리즘은 어렵다고만 생각했는데, 막상 하나하나 뜯어보다보니 너무 겁을 먹고 있었나 싶기도 하다 :) 차근차근 익숙해져보기로!!