[자료구조] Linked List와 Array List의 차이점

연결 리스트와 배열 리스트의 차이점

일반적인 배열 리스트

arr = [1, 2, 3, 4, 5] 라는 배열이 있을 때, 2와 3 사이의 6이라는 값을 새로 넣는다면 insert를 사용하게 된다.
이때 6이 arr[2] 자리에 새로 오게되고 뒤에 위치한 값들은 모두 한칸씩 뒤로 밀리면서 최대 O(n) 시간복잡도가 걸리게 된다.

하지만 연결리스트의 경우 아래와 같이 이전 노드와 다음 노드 정보가 포함된 노드들이 연결되어 있는 형태이다.

class Node:
    def __init__(self):
    	self.val = None
        self.prev = None
        self.next = None
        
[1] -- [2] -- [3] -- [4] -- [5]

따라서 새로운 노드를 중간에 삽입한다면 아래와 같이 삽입할 노드와 삽입할 위치의 이전, 이후 노드의 연결 정보만 변경하면 되기 때문에 O(1) 상수 시간복잡도를 갖는다.

[1] -- [2]   [3] -- [4] -- [5]
		 \	 /
		  [6]