[Java / 자료구조] Array v.s. LinkedList

자료구조를 알고, 알고리즘 문제를 풀 때 시간 복잡도 계산을 한다고 하는데, 시간 복잡도는 무엇이고 어떻게 계산하는지에 대해서 먼저 간단하게 알고 넘어가보도록 하자.

https://hyun0zinlog.tistory.com/112

[자료구조] 알고리즘, 시간 복잡도 / 공간 복잡도

 

---

그렇다면 ArrayList에서의 시간 복잡도는 어떻게 될까?

위 그림과 같이, size가 4인 array에 1,2,3,4 각각을 하나씩 추가할 경우, 마치 O(1)처럼 보인다.

하지만, 5라는 데이터를 추가로 넣을 경우, size가 8인 두 배 크기의 배열을 만들고, 기존 배열을 복사해야하므로 O(N)의 시간 복잡도를 갖니다.

따라서 수행하는 동작 원리를 따져보았을 때, O(1) 처럼 작동하지만, O(n)인 경우도 있다.

→ 이때 사용하는 표현 “amortized O(1)”

이는 n번 진행하면 O(1)처럼 작동한다. 하지만 중간에 있는 배열의 크기를 늘려주고 복사해가는 상황 때문에 O(1)이라고 하면 틀린 표현이 된다.

 

분할 상환 분석(amortized analysis) 이란?

"최악의 경우에 대해 최악의 경우가 발생하도록 연속된 연산을 수행하고, 그때의 한번의 연산에 대한 평균수행시간을 분석하는것"

동적 배열에서 데이터를 추가하는 시간 복잡도는 O(1)이다.
더블링이 일어났을 경우, 시간 복잡도는 O(N)이 된다.

이런 경우, 분할 상환 분석을 이용하여, 최악의 경우를 여러번에 걸쳐 골고루 나눠주는 형태로 시간 복잡도를 계산한다.
이때의 시간 복잡도를 Amortized O(1)이라고 표현한다.

---

 

그렇다면, 이제 본격적으로 LinkedList가 무엇인지에 대해 알아보자.

LinkedList

: 데이터가 자료의 주소 값으로 서로 연결(Link)되어 있는 구조를 의미한다.

LinkedList의 특징

• 자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로 위치하고 있는 원소의 주소를 연결하여 하나의 전체적인 자료구조를 이룬다.
  • 논리적 순서 : 사람이 이해하는 구조
  • 물리적 순서 : 실제 컴퓨터 메모리 상에 저장되는 구조
• 링크를 통해 원소에 접근하므로, 순차 리스트와 같이 물리적인 순서를 맞추기 위한 작업이 필요하지 않다.
• 자료구조의 크기를 동적으로 조정할 수 있어, 메모리의 효율적인 사용이 가능하다.

Node와 Head의 개념

노드(Node)

: 연결 리스트에서 하나의 원소에 필요한 데이터를 갖고 있는 자료 단위

• 데이터 필드
  • 원소의 값을 저장하는 자료구조
  • 저장할 원소의 종류나 크기에 따라 구조를 정의하여 사용
• 링크 필드
  • 다음 노드의 주소를 저장하는 자료구조

헤드(Head)

: 리스트의 시작 위치에 해당하는 노드

 

---

Array v.s. LinkedList

	Array	LinkedList
장점	random access, 무작위 접근 가능	빠른 자료 삽입, 삭제 가능
단점	크기 조절 불가. 느린 자료 삽입, 삭제	무작위 접근 불가

LinkedList의 특징

• 인덱스로 접근 불가
• 나 바로 뒤에 어떤 값이 있는지만 안다.
• 시작은 무조건 인덱스 0부터 시작. 이후 인덱스 2 값 알고 싶으면 두 칸 뒤로 이동. -> O(n) 걸림
• 하지만 삽입, 삭제 시, O(1)

LinkedList 종류

단순 연결 리스트 (Single LinkedList)

: 각 노드에서 단방향으로 연결되는 리스트

• 가장 앞, 뒤 노드는 쉽게 접근 가능하지만, 중간 노드 접근이 복잡한 단점 존재

 

이중 연결 리스트 (Double LinkedList)

: 각 노드에서 양방향(선행, 후행)으로 연결되는 리스트

• 양 방향 접근이 용이하지만, 메모리를 추가적으로 사용

단순 연결 리스트 데이터 삽입, 삭제

단순 연결 리스트 데이터 삽입

: 기존 리스트의 연결 관계는 유지하고, 새로운 노드만 연결

• 첫 번째 노트로 삽입하는 알고리즘

addFirst(L, i){        //  리스트 포인터 L, 원소 i
    new <- createNode(); // 새로운 노드 생성
    new.data = i;        // 데이터 필드 작성
    new.link = L;        // 링크 필드 작성
    L = new;             // 리스트의 처음으로 지정
}

• 가운데 노드로 삽입하는 알고리즘
  : 노드 pre의 다음 위치에 노드 삽입

add(L, pre, i) {         // 리스트 L, 노드 pre, 원소 i
    new <- createNode();   // 새로운 노드 생성
    new.data = i;          // 데이터 필드 작성
    if(L == NULL) {
        L = new;
        new.link = NULL;
    } else {
        new.link = pre.link;
        pre.link = new;
    }
}

• 마지막 노드로 삽입하는 알고리즘

addLast(L, i) {          // 리스트 L, 원소 i
    new <- createNode();   // 새로운 노드 생성
    new.data = i;
    new.link = NULL;

    if(L == NULL){        // 빈 리스트일 경우, 최초 노드 추가
        L = new;
        return;
    }

    temp = L;                 // 노드 링크 이용하여 리스트 순회

    while(temp.link != NULL){ // 마지막 노드 찾을 때까지 이동 
        temp = temp.link;
    }

    temp.link = new;          // 마지막 노드 추가
}

 

단순 연결 리스트 데이터 삭제

• 노드를 삭제하는 알고리즘
  : 노드 pre의 다음 위치에 있는 노드 삭제

delete(L, pre){               // 리스트 L, 노드 pre
    if(L == NULL) error;
    else{
        target = pre.link;        // 삭제 노드 지정
        if(target == NULL) return;
        pre.link = target.link;
    }
    freeNode(target)            // 할당된 메모리 반납
}

 

출처
https://inpa.tistory.com/entry/DS-%F0%9F%A7%B1-Circular-Doubly-LinkedList-%EC%A7%81%EC%A0%91-%EA%B5%AC%ED%98%84-%ED%95%B4%EB%B3%B4%EA%B8%B0-JAVA

https://www.geeksforgeeks.org/doubly-linked-list-tutorial/

https://jeffrytandiono.medium.com/amortized-analysis-ba6ad7724780

https://lsh424.tistory.com/70