[자료구조] Linkedlist, Array

Linkedlist란?

연결 리스트(Linkedlist)는 각 노드가 데이터와 포인터를 가지고 한줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.
데이터를 담고있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전 노드와의 연결을 담당하게 된다
- wikipidea

• 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조이다.
• 삽입과 삭제 : O(1) (삭제의 경우 특정 노드를 아는 경우에는 1이지만, 모르는 경우에는 n만큼의 시간이 소요된다.)
• 탐색 : O(n)

연결 리스트의 가장 첫 번째 지점을 Head라고 부른다. 마지막 노드는 Null을 가리킨다.

 

장단점

장점

• 연결 리스트는 데이터 구조의 큰 틀을 바꾸지 않고 노드를 추가하거나 삭제하기 쉽다.
• 연결 리스트는 배열과는 다르게 메모리가 연속적이지 않아도 된다. 왜냐하면 각 노드들은 데이터와 다음 노드의 포인터를 가지고 있기 때문이다.

단점

• 연결 리스트는 탐색이 느리다. 배열과 달리, 연결리스트는 데이터에 무작위 접근(Random access)을 할 수 없기 때문. 노드들은 첫 번째 노드부터 순차적으로 접근해야 한다
• 각 노드들은 포인터를 담고 있기 때문에 배열보다 더 큰 메모리를 사용한다.

Linkedlist의 종류

• 단일 연결 리스트(Singly Linked Lists) : 각 노드는 하나의 포인터만 가집니다. 우리가 위에서 이야기한 유형이 단일 연결 리스트입니다.
• 이중 연결 리스트(Doubly Linked Lists) : 각 노드는 2개의 포인터를 가지는데, 하나는 다음 노드를 그리고 나머지 하나는 이전 노드를 가르킵니다.
• 원형 연결 리스트(Circular Linked Lists) : 연결 리스트를 응용한 유형으로, 마지막 노드의 포인터가 첫 노드 또는 특정 노드를 가르키고 있는 마치 루프 형태를 가지는 유형을 말합니다.

Array란?

배열은 번호(인덱스)와 번호에 대응하는 데이터들로 이루어진 자료 구조를 나타낸다. 일반적으로 배열에는 같은 종류의 데이터들이 순차적으로 저장되어, 값의 번호가 곧 배열의 시작점으로부터 값이 저장되어 있는 상대적인 위치가 된다.
- wikipidia

• 배열은 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합입니다. (또한 중복을 허용하고 순서가 있다)
• 탐색 : O(1) 인덱스를 통해 랜덤 접근이 가능하다
• 삽입과 삭제 : O(N)

LinkedList랑 Array 간단 요약

Array, 즉 배열은 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조를 의미합니다. 메모리 상에서 연속적으로 저장되어 있는 특징을 갖기 때문에, Index를 통한 접근이 용이합니다.

배열은 인덱스를 통한 빠른 접근이 가능하지만, 삽입/삭제의 경우 시간 복잡도가 O(n)이기 때문에 오래걸리며, 배열 중간에 있는 데이터가 삭제 되면 공간 낭비가 발생합니다.

LinkedList는 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이며, 첫번째 노드를 Head, 마지막 노드를 Tail이라고 한다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있습니다. 배열과는 다르게 순차적으로 접근해야 하는 면에서 불리할 수도 있으나 노드가 연결된 구조이기 때문에 삽입과 삭제가 용이합니다.

따라서 배열은 빠른 접근이 요구되고, 데이터와 삽입과 삭제가 적을 때 사용하며, 연결 리스트는 삽입과 삭제 연산이 많고, 검색 빈도가 적을 때 사용합니다.

 

참조

https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8

https://opentutorials.org/module/1335/8821

https://www.nextree.co.kr/p6506/

https://ko.wikipedia.org/wiki/%EB%B0%B0%EC%97%B4