Into the new world

연결리스트의 3가지 기본 유형.

- 단일 연결
- 이중 연결
- 원형 연결

일반적인 단일 연결리스트의 구조는 아래와 같다.

typedef struct IntElement{
struct IntElement * next;
int data ;
}IntElement;

next 포인터를 구조체나 클래스의 맨 앞 쪽에 넣어두면 그 원소에 어떤 데이터가 들어가든 제대로 동작하는 포괄적인 리스트 처리 루틴을 더 쉽게 만들수 있다는 장점이 있다.

다른 언어에서는 임의의 객체에 대한 레퍼런스를 각 원소에 저장하는 식으로 연결 리스트 루틴을 만드는 것이 일반적.

public class ListElement{
ListElement next;
Object data;
public ListElement( Object data ){
 this.data = data;
}
}

 단일 연결리스트에서 전체 원소를 종주하려면 반드시 첫번째 원소의 위치를 알아야한다.

이중 연결리스트에서는 어디에서든 시작하면 된다.
원형 연결리스트( 테일 -> 헤드 ) 이런 구조.

기초적인 연결리스트(단일 연결리스트) 연산

헤드 원소 추적.
 단일 연결리스트에서 헤드에 대한 정보를 상실할 경우 접근 자체가 어려워지기 때문에 새로운 원소를 첫번째 원소 앞에 추가한다거나 리스트의 첫 번째 원소를 제거할 때 리스트의 헤드 포인터 또는 레퍼런스를 갱신해야 한다.

C/C++에서 종종 포인터를 잘못 사용하여 실수하는 일이 발생.

bool insertInFront(IntElement * head , int data)
{
 IntElement * newElem = new IntElement;
 newElem->data = data ;
 head = newElem;
 // 이렇게 할 경우 연결(리스트)가 생성되지 않음.
 return true;
}

헤드 포인터에 대한 지역 변수 사본만을 갱신하기 때문에 이 코드는 제대로
동작하지 않는다.

bool insertInForm(IntElement  **head, int data)
{
 IntElement* newElem = new IntElement ;
 newElem->data = data;
 *head = newElem;
 return true;
}

리스트의 종주시 반드시 체크해야 할 것.

리스트를 종주할 때는 반드시 연결 리스트가 끝났는지를 확인해야 한다.

원소의 삽입 및 삭제.

삭제 및 삽입을 하려면 삽입 또는 삭제할 위치의 바로 앞에 있는 원소에 대한 포인터 또는 레퍼런스가 필요하다.
bool deleteEle( IntElement ** head, IntElement * deleteMe)
{
IntElement * elem = *head;
if(deleteMe == *head )
{
// 헤드 일경우
// 따로 취급하는 이유. 헤드는 가장 상단에 위치 하므로 앞에 있는 원소와 뒤에있는 원소를 연결할 필요가 없다.
*head = elem->next;
delete deleteMe;
return true;
}

while(elem)
{
if(elem->next == deleteMe)
{
  // elem->next임에 주의하자.
  elem->next = deleteMe->next;
  delete deleteMe;
 return true;
 }
 elem = elem->next;
}
 return false;
}

리스트 전체를 지워야 할 경우
void deleteList(IntElement ** head)
{
IntElement * deleteMe = *head;
while(deleteMe)
{
 IntElement * next = deleteMe->next ;
 delete deleteMe;
 deleteMe = next;
}
*head = NULL;
}
이런식으로 2개의 포인터를 지정해 주어야 한다.