배열 (Array) & 리스트 (List)

1. Array (배열) ?

• 동일한 자료형의 데이터를 한꺼번에 관리하기 위한 자료구조이다.
• 배열을 이용하여 하나의 변수에 여러 데이터를 담을 수 있으며, 반복문을 이용하여 효율적으로 처리가 가능하다.

1-1. 배열의 특징

• 크기가 정해져 있기 때문에 바꾸지 못한다.
• 고유한 인덱스 값을 가지고 있으며, 인덱스를 통해 특정 위치의 데이터를 빠르게 조회할 수 있다.
• 데이터가 중간위치에서 추가 또는 삭제 될 경우, 빈번한 이동을 요구하며 남아있는 공간으로 인해 메모리 낭비가 발생할 수 있다.
• 특별한 기능이 없기 때문에 다른 자료구조의 부품으로 사용할 수 있다.

 

2. List (리스트) ?

• 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다.
• 노드의 포인터가 다음이나 이전의 노드와 연결되어 있다.

ex. 단순 연결 리스트

2-1. List 종류

• 포인터로 연결된 List이며, 세 종류가 있다.
  1. 단일 연결 리스트
  2. 이중 연결 리스트
  3. 원형 연결 리스트

2-1-1. 단일 연결 리스트

• 각 노드에 자료 공간과 한 개의 포인터 공간이 있으며, 각 노드의 포인터는 다음 노드를 가리킨다.

단일 연결 리스트의 구조

2-1-2. 이중 연결 리스트

• 단일 연결 리스트와 비슷하지만, 차이점은 포인터 공간이 두 개이며, 각 포인터는 앞 노드와 뒤의 노드를 가리킨다.

이중 연결 리스트의 구조

2-1-3. 원형 연결 리스트

• 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

단순 원형 연결 리스트의 구조

2-2. List의 특징

• 순서가 있는 데이터의 모임으로 시퀀스 (sequence) 라고 한다.
• 자료구조의 크기를 배열처럼 초기화 할 필요가 없다.
• 노드 중간위치에서 데이터의 추가 또는 삭제가 발생하여도 \(O(1)\) 만큼 시간복잡도가 소요되기 때문에 빠르게 진행된다.
• 데이터를 조회하는 경우, 배열처럼 인덱스를 통해 접근할 수 없어 시간복잡도는 \(O(n)\) 만큼 소요되기 때문에 느리다.

 

Code

ListNode 클래스

• 리스트를 구성하는 노드 클래스이다. 
• 클래스 변수로는 값을 저장하는 data, 이전과 다음 노드를 연결하는 next, prev 노드객체가 있다.

단일 연결 리스트 클래스

• 맨 처음인 head 노드와 리스트 크기를 클래스 변수로 넣어준다.

Insert 함수들

• 각각 head, tail, mid 위치에 노드를 삽입하는 함수들이다.

Remove 함수

Search 함수

 

Reference

• https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8#%EB%8B%A8%EC%9D%BC_%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8
• https://wayhome25.github.io/cs/2017/04/17/cs-18-1/