[11주차] 자료구조의 의미와 배열, 연결리스트

4월 2일 자 학습 내용 정리입니다.

 

 

✅ 자료구조

자료구조는 말 그대로 자료를 저장하는 구조이다.
자료구조에는 배열, 트리 등 여러 종류가 있으며 저장된 자료에 대해 접근하는 방법이 약간씩 다르다.

 

 

✅ 추상적 자료형

자료형이란 어떤 자료가 식별되는 방법을 정의하고 그 자료에 대한 여러가지 연산(동작)을 제공한다.
여기서 연산이란 그 자료에 어떻게 접근할 것인지, 그 자료를 어떻게 사용할 것인지 등 다양한 동작을 말한다.

추상적 자료형은 어떤 자료와 그 자료에 대한 연산(동작)들의 수학적인 정의를 의미한다.
하지만 이 정의를 구현하는 방법은 명시되어 있지 않다.

따라서 추상적 자료형은 자료들과 그 자료들에 대한 연산들을 개념적으로 정의만 한 것을 말하며 자료구조는 추상적 자료형을 구체적으로 구현해 자료를 저장하는 방법과 자료에 적용할 수 있는 연산을 제공한 것이다.

 

 

✅ 리스트

리스트는 추상적 자료형으로 리스트가 담는 자료는 순서가 존재하고 일렬로 나열된 값들이다.
리스트가 제공하는 연산은 크게 세 가지가 있는데 조회, 삽입, 삭제이다.

 

• 조회 : 임의의 위치에 존재하는 자료가 무엇인지 알아본다.
• 삽입 : 임의의 위치에 자료를 추가한다.
• 삭제 : 임의의 위치의 자료를 제거한다.

 

✔️ 배열

이 리스트라는 추상적 자료형을 구현한 대표적 예시가 배열(Array)이다.
배열에 저장되는 값들은 인덱스(index)라는 순서를 나타내는 번호를 가진다.

배열의 연산은 인덱스를 가지고 이루어진다.

 

배열 조회

조회의 경우 해당하는 인덱스가 가진 값을 알아보기만 하면 되니 비교적 단순한 작업이다.

 

배열 삽입

하지만 삽입의 경우 약간 번거롭게 느껴질 수 있다. 
새로운 자료를 배열의 중간에 추가할 경우 우선 배열의 제일 마지막 인덱스에 빈 공간을 추가로 만들고 삽입하고자 하는 인덱스를 비워주기 위해 그 뒤에 위치한 자료들의 순서를 변경해 주어야 하기 때문이다.

 

배열 삭제

삭제는 삽입과 반대로 진행된다.
우선 값을 제거할 인덱스의 공간을 비워주고 그 뒤에 위치한 자료들을 앞당겨준 뒤 제일 마지막에 위치한 빈 공간을 지워준다.

 

✔️ 연결리스트

배열 외에도 리스트라는 추상적 자료형을 구현한 예시로 연결 리스트(Linked List)가 존재한다.
배열은 각 자료에 인덱스를 붙여 저장하는 반면 연결 리스트는 여러 개의 노드(node)를 저장하는 방식으로 구현한다.

 

노드

노드는 자료와 포인터를 가진다.
자료는 노드가 저장하는 값 자체를 의미하며 포인터는 다음 순서의 노드를 가리킨다.
즉, 포인터가 인덱스의 역할을 하는 것이다.

 

연결리스트 조회

이러한 특성때문에 연결리스트는 조회하는 것이 번거롭다.
특정 위치의 자료를 찾기 위해서는 맨 처음 위치한 노드부터 포인터가 연결된 곳으로 넘어가며 자료를 찾아야 하기 때문이다.
배열이 찾는 자료가 어디 있는지에 관계없이 단번에 값을 찾는 것에 반해 연결 리스트는 찾는 자료의 위치가 시작점으로부터 멀수록 연산 횟수가 많아진다.

지금까지만 보면 배열 대신 왜 연결 리스트가 존재하는지 의문이겠지만 연결 리스트의 장점은 바로 삽입과 삭제이다.
자료를 삽입하고 삭제하기 위해 자료를 찾는 과정은 조회할 때처럼 번거롭지만 값을 찾고 나면 이야기가 달라진다.

 

연결리스트 삽입

우선 삽입의 경우 삽입하고자 하는 자료를 넣은 노드를 만든다.
그리고 삽입할 위치를 찾는다.
위치를 찾아왔다면 삽입할 위치 이전에 존재하는 노드의 포인터를 끊고 삽입할 노드에 연결한다.
그리고 삽입할 노드의 포인터를 원래 연결되어있던 노드와 이어준다.

 

연결리스트 삭제

삭제의 경우에도 마찬가지다.
삭제할 노드의 이전 노드와 삭제할 위치의 노드가 가리키고 있던 노드를 연결시켜준 뒤 해당 노드를 삭제하면 된다.

이러한 작업의 경우 값을 밀거나 당길 필요가 없기 때문에 편리하다.