자료구조 알고리즘 | Linked List

개념 : 물리적으로 떨어져 있는 노드들이 다음 노드의 주소값을 가지고 있어서 연결되는 형태
vs 배열 : 물리적으로 한공간에 배열의 크기만큼의 메모리 공간이 할당 되어 있음.
단점 : 노드의 주소값을 따라 접근해야 하기 때문에 접근속도가 느릴 수 있음
장점 : 노드를 추가하거나 삭제할때 한부분만 가진 주소값을 변경해주면 되기 때문에 비교적 간단
vs 배열 : 원소를 추가하거나 삭제하기 위해서는 배열 전체의 공간을 다시 할당 해야하기 떄문에 복잡
=> 크기가 정해지지 않은 데이터들, 추가 삭제가 잦은 데이터를 다룰때 용이하다.

단방향/양방향 Linked List

단방향 : 각 노드에 다음 노드에 대한 정보만 있어서 이전 노드로 이동할 수 없고 한쪽 방향으로만 이동할 수 있는 Linked List

⇒ 검색 시에 가장 앞의 노드부터 한개의 노드 씩 이동하면서 검색을 수행함.

양방향 : 각 노드의 전후 노드의 주소를 모두 가지고 있는 Linked List

⇒ 가장 끝에 노드를 삽일 할 때 제일 앞의 노드부터 찾아가야 하는 번거로움을 줄일 수 있음.

단방향 Linked List는 첫 노드의 주소만을 저장하고 양방향 Linked List는 처음과 끝 노드의 주소를 저장한다.

공간의 효율성을 고려해서 필요한 형태를 이용하는것이 좋다.