list란?

: 데이터 간 양방향으로 연결되어 있는 구조를 가지고 있는 자료구조

특징

1) 인덱스 접근이 불가능하다.
2) 포인터를 이용해 접근가능하다.
3) 데이터 크기가 가변적이다.
4) 중간에 데이터 삽입 및 삭제가 가능하다.
5) 앞에서도 데이터를 삽입 및 삭제가 가능하다.
6) 컨테이너의 원소들이 불연속적인 메모리를 가지고 있다.

장점

1) 포인터를 이용해 접근하므로 어느 곳에서든 쉽게 메모리 삽입 및 삭제가 가능하다.
2) 동적이므로 크기가 정해져 있지 않음
3) 불연속적인 메모리로 인한 메모리 관리가 편리??

단점

1) 인덱스 접근 불가능하므로 접근성 떨어진다.
2) 인덱스 접근 시 iterator가 반드시 필요하므로 벡터나 배열보다
iterator (왜 12바이트인지는 모르겟음..) 메모리를 하나 만들어주어야 한다.

어떻게 구현할 것인가?

구조체 내에 data와 앞과 뒤 를 양방향으로 연결한 구조체 포인터 2개 추가한다.
그리고 머리부분과 꼬리를 나타낼 2개의 포인터 변수를 더미노드(데이터 없고, 메모리 주소만 자기고 있는 데이터)로 만든 후에 진행!

• 앞 부분에 삽입 시키기
  

코드 :

• 뒷부분에 삽입하기
  

코드 :

• head 부분 제거하기
  

코드 :

• tail 부분 지우기
  

구현해보기

#include <string>
#include <iostream>
#include <vector>
#include <list>
using namespace std;

#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
	int data;
	struct Node *prev;
	struct Node *next;
} ;
Node *head, *tail;

//앞부분에 삽입하기 
void insert_head(int data)
{
	Node *node = new Node();
	node->data = data;
	node->prev = head;
	node->next = head->next;

	Node * next_Node = head->next;
	next_Node->prev = node;
	head->next = node;

}

//뒷부분에 삽입하기 
void insert_tail(int data)
{
	Node * node = new Node();
	node->data = data;
	node->next = tail;
	
	Node * prev_Node = tail->prev;
	node->prev = prev_Node;
	tail->prev = node;
	prev_Node->next = node;


}

//앞부분 제거하기 
void delete_head()
{
	Node * DEL = head->next;

	if (DEL->next == nullptr) return;
	head->next = DEL->next;
	DEL->next->prev = head;
	delete DEL;
}

//뒷부분 제거하기 
void delete_tail()
{
	Node *Del = tail->prev;

	if (Del->prev == nullptr) return;
	tail->prev = Del->prev;
	Del->prev->next = tail;
	delete Del;
}

//중간 삽입하기 

void print()
{
	Node * cur = head->next;
	while(cur != tail)
	{
		cout << cur->data << endl;
		cur = cur->next;
	}
}

int main() {	
	
	head = new Node();
	tail = new Node();

	head->prev = nullptr;
	tail->next = nullptr;
	head->next = tail;
	tail->prev = head;

	insert_head(17);
	insert_head(14);
	insert_head(15);

	insert_tail(4);
	insert_tail(5);
	insert_tail(6);

	insert_head(16);

	print();

	
	cout << "뒤쪽 제거하기" << endl;


	delete_tail();
	delete_tail();
	delete_tail();
	

	//cout << "앞쪽 제거하기" << endl;
	//delete_head();
	//delete_head();
	//delete_head();
	

	print();


	system("pause");

	return 0;
}

stl로 사용해보기

#include 는 추가해야 한다.

• 인덱스 접근은 불가능하다...
  

  선언된 list의 주소값은 알수 있다.
  //시작 주소값이라고 말할수 있는지는 생각좀...
  
  

• auto 접근은 가능
  

• iterator 사용방법
  : 잘 사용하지 않으니 주의하도록 하자.

  비교 연산자 사용하지 않는다.
  

  부등호 연산자를 이용한다.
  여기서 알수 있는 점
  -> 이터레이터 자체는 출력연산자에 대한 오버로딩 함수가 없다.
  -> 이터레이터는 stl 컨테이너를 가리키는 포인터값이라는 것을 알 수 있다.

  • 이상 있음
    
  • 이상 없음
    
    

• 컨테이너의 원소들의 메모리값이 불연속적이다.

  • 추가적으로 알수 있는점
    원소 가리키기 위해서는 새롭게 iterator를 사용해야 하므로
    순환시에는 12바이트?? 크기의 메모리를 하나 할당해주었다
    //왜 12인지는 모르겠다..
    

• 어떤 자료형을 가리키든 iterator 크기는 동일한 듯....