[자료구조] 배열 과 링크드리스트

최근까지 해시테이블에 대해 공부를 했는데 거기에서 배열과 링크드리스트에 관한 내용이 나와있어서 한번 정리해보고자 한다.

(끄적끄적)

배열

• 특정 크기만큼 연속된 메모리 공간에 데이터를 저장하는 구조
• 메모리상에서 연속적으로 저장되어 있는 특징을 갖기때문에, index를 통한 접근이 용이하다.
• 배열의 크기는 처음 생성할 때 정하며 이후에는 변경할 수 없다.

과정예시 그림

⬆️ 위 그림처럼 연속된 공간에 메모리를 확보하여 데이터를 저장할 수 있게 된다.

특징

1) 위 그림처럼 연속된 공간에 데이터들이 나열되어 있기 때문에 처음 주소만 알면 다른 위치도 손쉽게 알 수 있어용 ~ 그렇기에 랜덤으로 접근하는 것이 가능 합니다!

2) 배열은 특정 데이터를 O(1)로 조회할 수 있다. ( 단, 접근하고자 하는 인덱스를 알고있어야 한다. 순차적으로 탐색시에는 O(n) )

추가 및 삭제는 O(n)

• 데이터를 추가하거나 삭제할 때는 효율적이지 못함
• 데이터를 중간에 추가려하고 한다고 하면 추가하려고 하는 자리를 비우고 뒤에 있는 데이터를 한 칸씩 뒤로 밀어야하기 때문이다.
• 삽입 지점 이후의 데이터를 옮겨야 한다.
• 배열의 끝에 삽입 및 삭제는 O(1)

그래서 저번 글들을 보면 해시테이블에서 인덱스값이 충돌 나는것을 볼 수 있었다.

(ㅋㅋㅋㅋㅋ)

그래서 우리는 분리 연결법으로 충돌을 해결할 수 있다고 글에 적었는데 그게 링크드리스트이다. 한번 살펴보자

링크드리스트

• 링크드 리스트는 배열과 다르게 연속된 메모리 공간에 저장되어 있지 않다.
• 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조
• 첫번째 노드를 헤드(Head), 마지막 노드를 테일(Tail) 이라고 한다.
• 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져있다.
• 배열과는 다르게 순차적으로 접근해야 하는 면에서 불리할 수도 있으나, 노드가 연결된 구조이기 때문에 삽입, 삭제에 용이하다.

과정예시

• 각각의 데이터가 메모리공간 상에 고유한 노드 로 존재
• 그 노드는 자신의 앞에 있는 데이터와 뒤에 있는 데이터에 대한 주소를 기억하고 있다.

만약에 연결 리스트에 저장되어 있는 특정 데이터를 조사하려고 한다면 처음부터 순차적으로 탐색해야한다.

왜 ? → 노드는 연속된 메모리 공간에 존재하지 않고 모두가 떨어져 있기 때문

• 탐색을 위해서는 각 노드가 기억하고 있는 앞의 데이터와 뒤의 데이터 주소에 의지할 수 밖에 없다.
• 따라서 연결 리스트는 특정 데이터를 O(n)으로 조회한다.

저런 방법으로 링크드 리스트를 통해 Next node 값을 지정해줘서 충돌하는것을 피해주었지요 😚

배열의 장단점

• 장점 : 인덱스를 통한 빠른 접근 가능
• 단점
  1) 삽입과 삭제가 오래 걸린다
  2) 배열 중간에 있는 데이터가 삭제되면 공간 낭비 발생
• 용도로는 빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을 때 사용!

링크드리스트의 장단점

• 장점 : 삽입과 삭제가 용이하다.
• 단점 : 임의 접근이 불가능하고 처음부터 탐색을 해야한다.
• 용도 : 삽입과 삭제 연산이 많고 검색 빈도가 적을 때 사용!