리스트

Concept | List

🐢 Collection (여러 개의 원소들을 저장할 수 있는 자료구조)

: List, Set, Map

List, 선형 리스트: 순서 (Order)를 가진 항목들의 모임

Set (집합): 항목 간의 순서의 개념이 없음

    1. 순서 없음

    ex) (1,2,3)==(2,3,1)

    2. 중복을 허락하지 않음

    ex) (1,1,2,3,3)==(1,2,3)

Map: key와 value가 대응되는 원소를 나타낸다.

흔히 원소 표현은 인덱스로 한다.

cf) 대표적인 class in JAVA

    1. Hash table

    2. Hash map

 

! 우리가 일상에서 말하는 '버킷리스트'라던지 '위시리스트'는 자료구조에서의 list가 아니다?

--> 버킷리스트와 위시리스트 모두 순서가 중요하지 않은 나열이므로 list보다는 set이 맞는 개념

 

🐢 list 구현 방법

1. 배열을 이용하기

    - 장) 구현이 간단하다.

    - 단) 삽입, 삭제 시 overhead --> 배열의 특징: 같은 type 데이터 저장

    --> 연산 시, 삽입위치와 삭제위치 다음의 항목들을 모두 이동하여야 한다.

    - 단) 항목의 개수에 제한이 있다. (Static Memory Allocation) --> 배열의 특징: 연속된 메모리에 데이터 저장

// 배열로 구현된 리스트
const int MAX_LIST_SIZE=100;
int data[MAX_LIST_SIZE];			// int는 4byte이므로, 총 잡아둬야 하는 메모리 크기는 400byte
int length=0;				// 원소의 수가 현재 0이므로 해당 리스트는 비어있는 경우 (공백상태)
// int length=MAX_LIST_SIZE;		// 해당 리스트는 현재 포화상태

// ArrayList.h에서의 중요한 함수 일부

bool find(int item){
	for(int i=0;i<length;i++) if(data[i]==item) return true;
    return false;
}

void replace(int pos, int e){
	// pos의 입력이 잘못된 범위일 때 추가
	if(pos<0 || pos>MAX_LIST_SIZE) {
    	cerr<<"에러 범위"<<endl;
        return -1;
    }
    data[pos]=e;
}

int size(){return length;}

void display(){
	for(int i=0;i<size();i++) cout<<data[i];
    // size()보다 length가 더 좋다.
    // find와 display는 모두 ArrayList클래스 안에 public 멤버 함수이다.
    // 그러므로 자신의 private 멤버 변수 (length)에 접근 가능하다.
    // size()같이 함수를 호출하게 되면 overhead (context switch overhead)
    cout<<endl;
}

void insert(int pos, int e)){
	if(!isFull() && pos>=0 && pos<=length){			// pos==length일 때 -->가장 뒤에 넣기(add())
    	for(int i=length;i>pos;i--) data[i]=data[i-1];		// 뒤로 한 칸씩 밀기
        data[pos]=e;			// pos위치에 e 복사하기
        length++;			// 리스트 항목의 개수 증가
    }
	else cerr<<"포화상태 오류 또는 삽입 위치 오류"<<endl;
}

void remove(int pos){
	if(!isEmpty() && pos=>0 && pos<length){
    	for(int i=pos+1;i<length;i++) data[i-1]=data[i];		// 앞으로 한 칸씩 당기기
        length--;			// 리스트 항목의 개수 감소
    }
    else cerr<<"공백상태 오류 또는 삭제 위치 오류"<<endl;
}

2. linked list를 이용하기

    - 단) 구현이 복잡하다.
    - 단) traverse하는데 overload (시간이 오래 걸림)--> direct access가 안되기 때문이다.

    - 장) 삽입, 삭제가 효율적이다.

    --> 삽입연산

n->link=link;		// 1.
link=n;			// 2.

! 1과 2의 순서를 바꾸면 안된다.

    순서를 바꾸게 되면 link의 정보가 사라진다. (Memory leak)

 

    --> 삭제연산

removed=link;
link=removed->link;

! 1과 2의 순서를 바꾸면 안된다.

    - 장) 크기가 제한되지 않는다. (Dynamic Memory Allocation)

// linked list로 구현된 리스트
Node *head;				// 포인터 변수의 크기는 8byte이므로 메모리 8byte 잡아놓기

 

🐢 head pointer와 head node

head node: 포인터 변수가 아니라 Node 객체이다.

    - 맨 앞 노드의 삽입이나 삭제연산을 단순화 할 수 있다. --> head pointer이 NULL인지 아닌지 구분하지 않아도 된다.

// Node.h에서의 중요한 함수 일부

void setLink(Node *next) link=next;			//a.setLink(b)--> a노드 뒤에 b노드를 붙여라

void insertNext(Node *n){
	if(n!=NULL){
    	n->link=link;
        link=n;
    }
}

Node *removeNext(){
	Node *removed=link;
    if(removed!=NULL) link=removed->link;
    return removed;
}

// LinkedList.h에서의 중요 함수 일부

#include "Node.h"

class LinkedList{
private:
	Node org;			// head node
public:
	LinkedList():org(0){}		// org head node의 데이터 값을 0으로 초기화
    ~LinkedList(){clear();}
    
    Node *getHead(){return org.getLink();}
    bool isEmpty(){return getHead()==NULL;}
    // org.getLink()==NULL;
    
    void clear() {
    	while(!isEmpty()) delete remove(0);
    }
    
    // head node의 인덱스는 -1, 처음 노드의 인덱스는 0
    Node *getEntry(int pos){
    	Node *n=&org;
        for(int i=-1;i<pos;i++,n=n->getLink()) if(n==NULL) break;
    	return n;
	}
    
    void insert(int pos, Node *n){
    	Node *prev=getEntry(pos-1);
   		if(prev!=NULL) prev->insertNext(n);
    }
    
    void remove(int pos, Node *n){
    	Node *prev=getEntry(pos-1);
    	if(prev!=NULL) prev->removeNext();
    }
    
    Node *find(int val){
    	for(Node *p=getHead();p!=NULL;p=p->getLink()) if(p->hasData(val)) return p;
    	return NULL;
    }
    
    void replace(int pos, Node *n){
    	Node* prev=getEntry(pos-1);
    	if(prev!=NULL){
    		delete prev->removeNext();
    		prev->insertNext();
    	}
    }
    
    int size(){
    	int count=0;
    	for(Node *p=getHead();p!=NULL;p=p->getLink()) count++;
    	return count;
    }
};

 

🐢 linked list traverse

for(Node *p=head;p!=NULL;p=p->link)
for(Node *p=head;p->link!=NULL;p=p->link)

// p!=NULL 과 p->link!=NULL의 차이
// 루프를 벗어났을 때 전자는 p가 NULL, 후자는 p가 마지막 노드에 대한 포인터

// addLast를 구현하기 위해서는 후자를 사용

 

🐢 circular linked list

일반적인 circular linked list

변형된 circular linked list

- head pointer가 마지막 노드를 가리킨다.--> tail

- head와 tail에 모두 접근 하기 쉬워졌다.

 

🐢 doubly linked list

class Node2{
	int data;
    Node2 *prev;
    Node2 *next;			// 링크 필드가 2개 생김
}

p==p->next->prev==p->prev->next

 

- 삽입연산

void insertNext(Node2 *n){
	if(n!=NULL){
    	n->prev=this;				// 1
        n->next=next;				// 2
        // this->next와 next는 같다.
        // 1과 2는 순서를 바꿔도 상관없음
        
        if(next!=NULL) next->prev=n;		// 3
        next=n;				// 4
        // 3과 4는 순서 변경할 수 없음--> next의 정보가 사라진다.
    }
}

-삭제연산

// '현재 노드'를 linked list에서 제거하는 함수
// cf) simply linked list에서 removeNext()는 현재 노드의 다음 노드를 제거하는 함수
// --> prev 노드를 몰라서

Node *remove(){
	if(prev!=NULL) prev->next=next;			// 첫 노드가 아닌 경우
    // prev는 this->prev와 같다.
    if(next!=NULL) next->prev=prev;			// 마지막 노드가 아닌 경우
    return this;
}

// DbLinkedList.h
// LinkedList.h와 remove() 부분을 제외하고 모두 같은 코드

Node2 *remove(int pos){
	Node2* n=getEntry(pos);
    return n->remove();
}

void replace(int pos, Node2 *n){
	Node2 *prev=getEntry(pos-1);
    if(prev!=NULL){
    	delete prev->getNext()->remove();		// getNext하고 remove를 해줘서 현재 노드를 delete
        prev->insertNext(n);
    }
}

 

🐢 doubly linked list를 이용한 deque 구현하기

//LinkedDeque.h
#include "DbLinkedList.h"

class LinkedDeque:public DbLinkedList{
public:
	void addFront(Node *n){insert(0,n);}			// 0위치에 n을 넣어라
    Node2 *deleteFront(){return remove(0);}			// remove--> delete+return (pop과 유사)
    Node2 *getFront(){return getEntry(0);}			// peek과 같은 연산
    void addRear(Node *n)){insert(size(),n);}		// 제일 뒤에다가 노드 n을 넣어라
    Node2 *deleteRear(){return remove(size()-1);}
    Node2 *getRear(){return getEntry(size()-1);}	// peek같은 연산, 마지막 노드 리턴하기
};

 

🐢 Standard IO

stdout, stderr --> 콘솔에 출력하는 것이다. (stderr은 에러를 출력한다.)

stdin --> 키보드로 입력받는 것이다.