![[자료구조] 리스트 (ArrayList vs LinkedList)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FlfYX3%2FbtqSgNBtgYz%2FDHrngOnzImJUfZW9OUZYg0%2Fimg.png)
728x90
반응형
1. 리스트
1.1 리스트란?
리스트(List)란 앞에서 공부한 배열, 스택, 큐 등과 같은 선형 자료구조이다.
그렇다면 이들과 리스트의 차이점은 무엇일까?
스택과 큐의 경우 자료의 접근이 전단(front) 혹은 후단(rear)에 제한되어 있다.
하지만 리스트는 이러한 제한이 없다. 즉, 임의의 위치에 있는 항목에 접근이나 연산이 가능하다는 것이다.
1.2 배열 vs 리스트
배열(array) 또한 임의의 위치에 접근이 가능하다.
그렇다면 배열과 리스트의 차이는 무엇일까?
배열은 각각의 원소에 순서대로 index가 할당되어 있다.
위 배열에서 c 원소를 삭제하는 경우 아래와 같은 형태가 된다.
삭제한 c의 메모리 공간은 빈 공간으로 남아있으며, d와 e의 index는 변함이 없다.
만약 위의 행위가 리스트로 구현이 된다면 아래와 같은 형태가 된다.
더 이상 리스트에 c의 메모리 공간 자체가 존재하지 않는다.
덕분에 데이터 밀도가 촘촘해졌으며, 메모리 공간을 효율적으로 사용할 수 있게 되었다.
하지만 c 뒤에 위치하고 있었던 d와 e의 index가 변경되었다.
즉, 리스트에서는 index를 식별자로 사용할 수 없다.
위의 예제에서 봤듯이 리스트에서는 index가 중요하지 않다.
리스트에서 중요한 것은 원소들 간의 순서이다.
따라서 리스트를 다른 말로 시퀀스(sequence)라고도 한다.
수학에서의 유한수열(finite sequence)과 같은 개념이라고 생각하면 된다.
1.3 리스트 ADT
객체
- 임의의 위치에 접근이 가능한 동일한 자료형 요소들의 순서 있는 모음
연산
- insert(i, x) : i 위치에 새로운 요소 x 삽입
- delete(i) : i 위치의 요소를 삭제하고 반환
- getEntry(i) : i 위치의 요소를 반환
- find(x) : 리스트에 요소 x가 있는지 확인
- replace(i, x) : i 위치에 있는 요소를 x로 변경
- isEmpty() : 리스트가 비어있으면 true 아니면 false 반환
- isFull() : 리스트가 가득 차 있으면 true 아니면 false 반환
- size() : 리스트 내의 모든 요소 개수를 반환
- display() : 리스트 내의 모든 요소 출력
2. ArrayList
2.1 ArrayList란?
ArrayList는 배열을 이용하여 리스트를 구현한 것이다.
ArrayList를 구현하기 위해서는 크기가 정해진 1차원 배열이 필요하다.
이 배열에 리스트에 요소들이 순서대로 저장되는 것이다.
또한 배열 내에서 리스트의 범위를 알기 위해, 리스트에 저장된 요소의 개수를 나타내는 변수 length가 필요하다.
2.2 ArrayList 구현 (C++)
#include <iostream>
using namespace std;
#define MAX_LIST_SIZE 100
template <typename T>
class ArrayList {
private:
T data[MAX_LIST_SIZE];
int length;
public:
ArrayList(){
length = 0;
}
~ArrayList(){}
// [삽입] list의 idx번째에 요소 x 추가
void insert(int idx, T x){
if(isFull()){
cout << "List full error" << endl;
return;
}
if(idx<0 || idx>length){
cout << "insert index error" << endl;
return;
}
for(int i=length; i>idx; i--){ // idx 뒤의 요소들을 한칸씩 뒤로 이동
data[i] = data[i-1];
}
data[idx] = x; // idx번째에 x 대입
length++;
}
// [삭제] idx번째 요소를 리스트에서 제거 후 반환
T remove(int idx){
if(isEmpty()){
cout << "List empty error" << endl;
exit(EXIT_FAILURE);
}
if(idx<0 || idx>length){
cout << "remove index error" << endl;
exit(EXIT_FAILURE);
}
T x = data[idx]; // 삭제될 요소
for(int i=idx+1; i<length; i++){ // idx 뒤의 요소들을 한칸씩 앞으로 이동
data[i-1] = data[i];
}
length--;
return x;
}
// idx번째 항목 반환
T getEntry(int idx){
return data[idx];
}
// 요소 x가 리스트에 있는지 확인
bool find(T x){
for(int i=0; i<length; i++){
if(data[i] == x){
return true;
}
}
return false;
}
// idx번째 요소를 x로 변경
void replace(int idx, T x){
data[idx] = x;
}
// List size 반환
int size(){
return length;
}
// List 출력
void display() {
cout << "List : ";
for(int i=0; i<size(); i++){
cout << "[" << data[i] << "]";
}
cout << endl;
}
bool isEmpty(){
return length == 0;
}
bool isFull(){
return length == MAX_LIST_SIZE;
}
};
int main(){
ArrayList<char> list;
cout << "===== insert list x5 =====" << endl;
list.insert(0, 'a');
list.insert(1, 'b');
list.insert(2, 'c');
list.insert(list.size(), 'd'); // list 마지막에 'd' 삽입
list.insert(4, 'e');
cout << "size : " << list.size() << endl;
list.display();
cout << "===== remove index3 =====" << endl;
list.remove(3); // 3번째 요소 삭제
cout << "size : " << list.size() << endl;
list.display();
cout << "===== insert 'f' at index1 =====" << endl;
list.insert(1, 'f');
cout << "size : " << list.size() << endl;
list.display();
cout << "===== replace 'g' at index0 =====" << endl;
list.replace(0, 'g');
list.display();
return 0;
}
2.3 [번외] Java에서의 ArrayList (java.util.ArrayList)
ArrayList는 Java에서 가장 많이 사용되는 자료구조 중 하나이다.
Java에서 기본적으로 제공하는 ArrayList에 대해 알아보자.
import java.util.ArrayList;
ArrayList<Integer> lists = new ArrayList<>();
ArrayList 사용 예시
lists.add(10);
lists.add(20);
lists.add(1, 40); // 1번째에 40 추가
lists.remove(1); // 리스트의 1번째 요소 삭제
lists.get(0); // 리스트의 0번째 요소 반환
ArrayList를 사용함에도 최대 배열 size를 지정하지 않았다.
왜 그럴까?
Java의 ArrayList는 내부적으로 배열의 크기가 고정되어 설정된다.
만약 배열이 가득 찼음에도 새로운 데이터가 추가된다면, 기존의 배열보다 1.5배 긴 새로운 배열을 만들어 기존 리스트 데이터를 새로운 배열로 복제한다.
하지만 이러한 경우 당연히 시간이 오래 걸리기 때문에 프로그래머는 이를 고려하여 ArrayList를 사용해야 한다.
3. Linked List
3.1 Linked List란?
Linked List는 Node 간의 연결(Link)을 이용하여 동적으로 크기를 할당할 수 있는 선형 자료구조이다.
Node는 데이터와 포인터를 가지고 있으며 각 Node의 포인터는 다음 Node 또는 이전 Node와의 연결을 담당한다.
3.2 Linked List 구조
각각의 Node는 data와 link 변수를 가진다.
data 변수에는 Linked List에서 사용할 자료형의 데이터가 들어가고, link 변수에는 다음 Node의 메모리 주소값이 들어간다.
head pointer란 첫 번째 Node의 주소를 가리키는 변수를 뜻한다.
3.3 ArrayList vs LinkedList
ArrayList와 LinkedList의 차이점을 알아보자.
3.4 Linked List 종류
Singly Linked List (단일 연결 리스트)
Singly Linked List는 각 노드에 data와 한 개의 포인터 변수가 있고, 각 노드의 포인터는 다음 노드를 가리킨다.
Circular Linked List (원형 연결 리스트)
Circular Linked List는 Singly Linked List와 동일하지만 마지막 노드의 포인터가 처음 노드를 가리킨다.
우리가 앞에서 다뤘던 Circular Queue처럼 원형 구조의 리스트가 된다.
Doubly Linked List (이중 연결 리스트)
Doubly Linked List 또한 Singly Linked List와 비슷하지만, 각 노드에 2개의 포인터 변수가 있다.
각각의 포인터는 이전 노드와 다음 노드를 가리킨다.
3.5 head pointer를 사용하여 LinkedList 구현 (C++)
Singly Linkedlist를 구현해보자.
LinkedList의 head를 표현하기 위해 head pointer 개념을 사용한다. (자세한 내용은 뒤에서...)
#include <iostream>
using namespace std;
// Node
template <typename T>
struct Node {
private:
T data;
Node<T>* next = nullptr;
public:
Node(T d, Node<T>* pNode){
data = d;
next = pNode;
}
~Node(){}
Node<T>* getNext() {
return next;
}
void setNext(Node<T>* pNode){
next = pNode;
}
T getData(){
return data;
}
};
template <typename T>
class SinglyLinkedList {
private:
Node<T>* head; // head pointer
int size = 0;
public:
SinglyLinkedList(){
head = nullptr;
}
~SinglyLinkedList(){}
// list 마지막에 data 삽입
void insert(T data){
Node<T>* node = new Node<T>(data, nullptr);
if(isEmpty()){ // 비어있는 경우 head에 node 추가
head = node;
}else{ // 아닌 경우 마지막 node를 찾아서 해당 node의 next에 새로운 node를 연결
Node<T>* prevNode = head;
for(int i=0; i<size-1; i++) {
prevNode = prevNode->getNext();
}
prevNode->setNext(node);
}
size++;
}
// list의 idx번째에 data 삽입
void insert(T data, int idx){
if(idx < 0 || idx > size){
cout << "index error" << endl;
return;
}
Node<T>* node = new Node<T>(data, nullptr);
if(idx==0){ // 0번째 index에 추가하는 경우
node->setNext(head); // 새로운 node의 next에 기존 head node를 연결 (비어있는 경우 nullptr로 들어감)
head = node; // 0번째 index가 바꼈기 때문에 head를 바꾸어줌
}else{ // 아닌경우
Node<T>* prevNode = head;
for(int i=0; i<idx-1; i++) {
prevNode = prevNode->getNext(); // index-1번째 node를 찾은 후
}
node->setNext(prevNode->getNext()); // 새로운 node의 next에 이전 node의 next를 대입.
prevNode->setNext(node); // 이전 node의 next에는 새로운 node를 연결
}
size++;
}
// idx번째 요소 삭제
void remove(int idx){
if(isEmpty()){
cout << "List is Empty" << endl;
return;
}
if(idx < 0 || idx > size){
cout << "index error" << endl;
return;
}
if(idx==0){ // 0번째 index를 지우는 경우 head를 다음노드로 바꿔줌
Node<T>* tmpNode = head;
head = tmpNode->getNext();
delete tmpNode;
}else{ // 아닌경우
Node<T>* prevNode = head;
for(int i=0; i<idx-1; i++) {
prevNode = prevNode->getNext(); // index-1번째 node를 찾은 후
}
Node<T>* tmpNode = prevNode->getNext();
prevNode->setNext(tmpNode->getNext()); // 해당 node의 next를 삭제할 node의 next로 바꿔줌
delete tmpNode;
}
size--;
}
// list 출력
void display(){
if(isEmpty()){
cout << "List is Empty" << endl;
return;
}
Node<T>* tmpNode = head;
while(tmpNode){
cout << "[" << tmpNode->getData() << "]";
tmpNode = tmpNode->getNext();
}
cout << endl;
}
bool isEmpty(){
return size==0 ? true : false;
}
};
int main(){
SinglyLinkedList<char> list;
cout << "===== insert x3 =====" << endl;
list.insert('a');
list.insert('b');
list.insert('c');
list.insert('d', 2); // insert 'd' at index2
list.display();
cout << "===== remove index1 =====" << endl;
list.remove(1);
list.display();
return 0;
}
3.6 head node를 사용하여 LinkedList 구현 (C++)
이번엔 head node 개념을 사용해서 구현해보자. (역시나 자세한 내용은 뒤에서...)
#include <iostream>
using namespace std;
// Node
template <typename T>
struct Node {
private:
T data;
Node<T>* next = nullptr;
public:
Node(){
data = T();
next = nullptr;
}
Node(T d, Node<T>* pNode){
data = d;
next = pNode;
}
~Node(){}
Node<T>* getNext() {
return next;
}
void setNext(Node<T>* pNode){
next = pNode;
}
T getData(){
return data;
}
};
template <typename T>
class SinglyLinkedList {
private:
Node<T> org; // head node
public:
SinglyLinkedList(){}
~SinglyLinkedList(){}
// first node 반환 (list의 head pointer)
Node<T>* getHead(){
return org.getNext();
}
// idx번째 항목 반환
Node<T>* getEntry(int idx){
if(idx<-1 || idx>size()){
cout << "index error" << endl;
exit(EXIT_FAILURE);
}
Node<T>* node = &org;
// head node부터 idx번 반복해서 next node를 찾아감
for(int i=-1; i<idx; i++){
node = node->getNext();
}
return node;
}
// list의 idx번째에 data 삽입
void insert(int idx, T data){
Node<T>* prev = getEntry(idx-1); // idx번째 node의 이전 node
Node<T>* node = new Node<T>(data, prev->getNext()); // 새로운 node의 next에 prev의 next를 대입
prev->setNext(node); // prev의 next에는 새로운 node의 주소 대입
}
// list의 idx번째 요소 삭제 및 반환
T remove(int idx){
if(isEmpty()){
cout << "List is Empty" << endl;
exit(EXIT_FAILURE);
}
Node<T>* node = getEntry(idx); // 삭제할 node
T data = node->getData(); // 삭제할 node의 data
Node<T>* prev = getEntry(idx-1); // idx번째 node의 이전 node
prev->setNext(node->getNext()); // prev의 next에 삭제할 node의 next 대입
delete node;
return data;
}
// list의 idx번째 요소를 data로 변경
void replace(int idx, T data){
Node<T>* prev = getEntry(idx-1); // 삭제될 node의 이전 node
Node<T>* node = new Node<T>(data, prev->getNext()->getNext()); // 새로운 node
delete prev->getNext();
prev->setNext(node);
}
// list 출력
void display(){
if(isEmpty()){
cout << "List is Empty" << endl;
return;
}
for(Node<T> *p = getHead(); p != nullptr; p=p->getNext()){
cout << "[" << p->getData() << "]";
}
cout << endl;
}
int size(){
int cnt = 0;
for(Node<T> *p = getHead(); p != nullptr; p=p->getNext()){
cnt++;
}
return cnt;
}
bool isEmpty(){
return size()==0 ? true : false;
}
void clear(){
while(!isEmpty()){
remove(0);
}
}
};
int main(){
// SinglyLinkedList<char> list;
//
// cout << "===== insert x3 =====" << endl;
// list.insert(0, 'a');
// list.insert(1, 'b');
// list.insert(2, 'c');
// list.display();
//
// cout << "===== insert 'd' at index2 =====" << endl;
// list.insert(2, 'd');
// list.display();
//
// cout << "===== remove index1 =====" << endl;
// list.remove(1);
// list.display();
SinglyLinkedList<int> list;
list.insert(0, 10);
list.insert(0, 20);
list.insert(1, 30);
list.insert(list.size(), 40);
list.insert(2, 50);
list.display();
list.remove(2);
list.remove(list.size()-1);
list.remove(0);
list.replace(1, 90);
list.display();
list.clear();
list.display();
return 0;
}
3.7 head pointer vs head node
LinkedList에서는 첫 번째 node의 주소를 관리하기 위해 head pointer를 사용한다.
하지만 head node를 사용하여 첫 번째 node를 가리킬 수도 있다.
head pointer
Class LinkedList{
Node* head;
...
head node
Class LinkedList{
Node org; // 실제 head point는 "org.link"
...
head pointer를 사용하는 경우 첫 번째 node인지 구별하여 첫번째 node에서 삽입, 삭제가 이뤄지는 경우 따로 처리를 해주어야 한다.
// list의 idx번째에 data 삽입
void insert(int idx, T data){
Node<T>* node = new Node<T>(data, nullptr);
if(idx==0){ // 0번째 index에 추가하는 경우
node->setNext(head);
head = node;
}else{ // 아닌경우
Node<T>* prevNode = head;
for(int i=0; i<idx-1; i++) {
prevNode = prevNode->getNext();
}
node->setNext(prevNode->getNext());
prevNode->setNext(node);
}
}
head node를 사용하면 실제 head 앞에 임의의 empty node가 있어 항상 동일한 logic으로 구현할 수 있다. → 삽입과 삭제 용이
// list의 idx번째에 data 삽입
void insert(int idx, T data){
Node<T>* prev = getEntry(idx-1); // idx번째 node의 이전 node
Node<T>* node = new Node<T>(data, prev->getNext()); // 새로운 node의 next에 prev의 next를 대입
prev->setNext(node); // prev의 next에는 새로운 node의 주소 대입
}head pointer를 사용한 code와 비교했을 때 확실히 간단해진 것을 볼 수 있다.
3.8 Circular Linked List
위에서 설명했듯이 Circular Linked List는 마지막 Node의 link가 첫 번째 Node를 가리키는 원형 구조의 리스트이다.
이러한 구조에서 가장 마지막 Node tail에 쉽게 접근하기 위해 head pointer가 tail Node를 가리키게 된다.
즉, 개념적으로 head pointer가 가리키는 Node가 tail Node이며, tail Node의 다음 Node가 head Node인 것이다.
3.9 Doubly Linked List
이중연결리스트 또한 위에서 설명했을뿐더러 이전에 deque를 구현해 보았으니, 바로 C++로 구현해보자.
#include <iostream>
using namespace std;
// Node
template <typename T>
struct Node {
private:
T data;
Node<T>* prev;
Node<T>* next;
public:
Node(){
data = T();
prev = nullptr;
next = nullptr;
}
Node(T d, Node<T>* prevNode, Node<T>* nextNode){
data = d;
prev = prevNode;
next = nextNode;
}
~Node(){}
Node<T>* getPrev() {
return prev;
}
void setPrev(Node<T>* pNode){
prev = pNode;
}
Node<T>* getNext() {
return next;
}
void setNext(Node<T>* pNode){
next = pNode;
}
T getData(){
return data;
}
};
template <typename T>
class DoublyLinkedList {
private:
Node<T> org; // head node
public:
DoublyLinkedList(){}
~DoublyLinkedList(){}
// first node 반환 (list의 head pointer)
Node<T>* getHead(){
return org.getNext();
}
// idx번째 항목 반환
Node<T>* getEntry(int idx){
if(idx<-1 || idx>size()){
cout << "index error" << endl;
exit(EXIT_FAILURE);
}
Node<T>* node = &org;
// head node부터 idx번 반복해서 next node를 찾아감
for(int i=-1; i<idx; i++){
node = node->getNext();
}
return node;
}
// list의 idx번째에 data 삽입
void insert(int idx, T data){
Node<T>* prev = getEntry(idx-1); // idx번째 node의 이전 node
Node<T>* node = new Node<T>(data, prev, prev->getNext()); // 새로운 node의 prev에는 prev, next에는 prev->next 대입
prev->setNext(node); // prev의 next에는 새로운 node 대입
if(node->getNext() != nullptr){ // node의 next가 null이 아닌 경우 next->prev에 새로운 node 대입
node->getNext()->setPrev(node);
}
}
// list의 idx번째 요소 삭제 및 반환
T remove(int idx){
if(isEmpty()){
cout << "List is Empty" << endl;
exit(EXIT_FAILURE);
}
Node<T>* node = getEntry(idx); // 삭제할 node
T data = node->getData(); // 삭제할 node의 data
Node<T>* prev = getEntry(idx-1); // idx번째 node의 이전 node
prev->setNext(node->getNext()); // prev의 next에 삭제할 node의 next 대입
if(node->getNext() != nullptr){ // node의 next가 null이 아닌 경우 next->prev에 삭제할 node의 prev 대입
node->getNext()->setPrev(prev);
}
delete node;
return data;
}
// list의 idx번째 요소를 data로 변경
void replace(int idx, T data){
Node<T>* prev = getEntry(idx-1); // 삭제될 node의 이전 node
Node<T>* node = new Node<T>(data, prev, prev->getNext()->getNext()); // 새로운 node
delete prev->getNext();
prev->setNext(node);
if(node->getNext() != nullptr){
node->getNext()->setPrev(node);
}
}
// list 출력
void display(){
if(isEmpty()){
cout << "List is Empty" << endl;
return;
}
for(Node<T> *p = getHead(); p != nullptr; p=p->getNext()){
cout << "[" << p->getData() << "]";
}
cout << endl;
}
int size(){
int cnt = 0;
for(Node<T> *p = getHead(); p != nullptr; p=p->getNext()){
cnt++;
}
return cnt;
}
bool isEmpty(){
return size()==0 ? true : false;
}
void clear(){
while(!isEmpty()){
remove(0);
}
}
};
int main(){
DoublyLinkedList<int> list;
list.insert(0, 10);
list.insert(0, 20);
list.insert(1, 30);
list.insert(list.size(), 40);
list.insert(2, 50);
list.display();
list.remove(2);
list.remove(list.size()-1);
list.remove(0);
list.replace(1, 90);
list.display();
list.clear();
list.display();
return 0;
}
728x90
반응형