자료구조 - 선형자료구조 (연결리스트)

선형자료구조란 요소가 일렬로 나열되어 있는 자료구조를 말한다.

 

연결리스트

: 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시키는 자료구조이다.

 

연결리스트의 종류

1. 단순 연결리스트

: 하나의 노드가 하나의 링크필드와 데이터를 갖고 있는 연결리스트이다.

 * 마지막 노드의 링크필드에는 null 값이 들어있다.

 

(그림으로 표현한 단순연결리스트이다.)

 

[ 단순 연결리스트의 삽입과 삭제 ]

 

• insert_first() : 리스트의 시작부분에 노드를 삽입하는 함수

1. 동적 메모리 할당을 통해 새로운 노드 p 생성
2. 노드 p->data 에 데이터 값을 저장
3. 노드 p->link 를 현재의 head 값으로 변경
4. head 를 p 값으로 변경
5. 변경된 헤드 포인터 반환

 

• insert() : 리스트의 중간부분에 노드를 삽입하는 함수

1. 동적 메모리 할당을 통해 새로운 노드 p 생성
2. 노드 p->data 에 데이터 값 저장
3. 노드 p->link 가 p 를 가리키게 변경 (p 는 삽입하고 싶은 위치 뒤에 있는 노드의 데이터값)
3. 노드 pre->link 가 p->link 가리키게 변경 (pre 노드는 삽입하고 싶은 위치의 선행 노드)
4. 변경된 헤드 포인터 반환

 

• delete_first() : 리스트의 시작부분의 노드를 삭제하는 함수

1. 헤드 포인터의 값을 removed 에 복사
2. 헤드 포인터의 값을 head->link 로 변경
3. removed 가 가리키는 동적 메모리를 반환
4. 변경된 헤드 포인터를 반환

 

• delete() : 리스트의 중간 부분의 노드를 삭제하는 함수

1. 삭제할 노드를 탐색 (removed)
2. removed->link 가 pre->link 를 가리키게 변경
3. removed 노드의 동적 메모리를 반납
4. 변경된 헤드 포인터 반환

 

2. 원형 연결리스트

: 마지막 노드가 첫번째 노드를 가리키는 리스트이다. 즉, 마지막 노드의 링크필드가 null 이 아닌 첫 번째 노드의 링크를 가지고 있다.

 

(그림으로 표현한 원형연결리스트이다.)

 

[원형 연결리스트의 삽입 ]

 

• insert_first() : 리스트의 시작부분에 노드를 삽입하는 함수

1. 새로운 노드의 링크인 node->link 가 첫 번재 노드를 가리키게 변경
2. 마지막 노드의 링크가 node 를 가리키게 변경

 

• insert_last() : 리스트의 마지막부분에 노드를 삽입하는 함수

* 원형리스트는 어차피 원형으로 연결되어 있기 때문에 어디가 처음이고 어디가 끝인지 불분명하다. 따라서 insert_first() 의 방법대로 노드를 삽입한 후 
head 의 위치만 새로운 노드로 바꾸어주면 새로 삽입된 노드가 마지막 노드가 된다.

 

3. 이중 연결리스트

: 특정 노드에서 양방향으로 자유롭게 움직일 수 있는 연결리스트이다.

이중 연결리스트는 하나의 노드가 두개의 링크필드 (선행 노드와 후속노드) 와 데이터를 가지고 있다.

 

(그림으로 표현한 이중연결리스트이다.)

 

[이중 연결리스트의 삽입과 삭제 ]

 

• insert() : 새로운 노드를 삽입하는 함수

// 새로운 데이터를 노드 before 의 오른쪽에 삽입한다고 가정

newnode->data = data;
newnode->llink = before;
newnode->rlink = before->rlink;
before->rlink->llink = newnode;
before->rlink = newnode;

 

• delete() : 노드를 삭제하는 함수

// 노드 removed 를 삭제한다고 가정

만약, removed == head 일 경우 노드가 없다는 것을 의미하므로 return
그것이 아니라면
removed->llink->rlink = removed->rlink;
removed->rlink->llink = removed->llink;
free(removed);