연결리스트(linked list)란?
-연결리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.
-각 노드는 다음 노드를 가리키는 포인터를 포함한다.
-다음 노드를 가리키는 포인터는 다음 노드의 주소를 값으로 가지고 있다.
-각 노드의 포인터 변수는 다음 노드의 데이터의 주소를 값으로 가진다. 또한 각 포인터 변수의 주소도 따로 존재한다.
단순연결리스트(singly linked list)의 구현
typedef struct _Node{
int data; /* 저장할 데이터 */
struct _Node* next; /* 다음 노드를 가리킬 포인터*/
}Node;각 노드는 저장할 데이터와 다음 노드를 가리킬 포인터로 이루어져 있다.
연결리스트의 초기화(init)
Node* head;
void init(){
head = NULL;
}가장 첫번째 노드를 가리킬 포인터 Node*head를 전역변수로 선언하고 init()함수를 통해 초기화한다.
연결리스트의 삽입(insert)
1. 가장 앞에 노드를 삽입하는 경우
연결리스트가 비어있다고 가정한다면 첫번째 노드로 정수 100을 데이터로 갖는 노드를 추가한다고 했을 때, 간단하게 newNode를 만든 후 head가 newNode를 가리키도록 하면 된다.
cf)연결리스트가 비어있는 것을 확인하기 위해서는 head == Null이라면 연결리스트가 비어있는 것이다.
연결리스트가 비어 있지 않다고 가정하면 newNode를 생성한 후 head가 가리키는 노드를 newNode의 next포인터가 가리키게 한다. 이후에는 head가 newNode를 가리키게 하면 끝난다.
2. 가장 뒤에 노드를 삽입하는 경우
마지막 노드로 정수 300을 데이터로 갖는 노드를 추가한다고 가정하면 newNode를 만든 후 마지막 노드의 next포인터가 newNode를 가리키게 하면 될 것이다.
3. 중간에 노드를 삽입하는 경우
연결리스트 중간에 정수 200을 데이터로 갖는 노드를 추가한다고 하면
-가장 먼저 newNode를 생성한다.
-newNode의 new포인터가 이전 노드의 next가 가리키는 노드를 가리키도록 한다.
-마지막으로 이전 노드의 next포인터가 new노드를 가리키도록 하면 된다.
연결리스트이 삭제(delete)
사용자가 data를 입력하여 해당 data를 갖는 노드를 연결리스트에서 삭제
- 가장 앞의 노드를 삭제하는 경우
head가 cur>>next를 가리키게 하고, cur>>next를 NULL로 설정한다.
이후 cur을 free시키면 완료된다.
- 가장 뒤의 노드를 삭제하는 경우& 중간 노드를 삭제하는 경우
prev라는 포인터를 이용해 삭제할 노드의 이전 노드를 가리켜야한다.
초기에 prev 포인터와 cur포인터는 모두 head가 가리키는 첫번째 노드를 가리킨다.
이후 cur포인터가 다음 노드를 가리키고, 이때 사용자가 입력한 데이터200과 cur>>data가 일치하므로 삭제과정을 진행한다.
prev>>next가 cur>>next를 가리키게 하고, 이후 cur>>next는 NULL을 가리키게 한다.
이후에는 cur을 free해주면 삭제가 완료된다.
