1. 연결 리스트의 개념
리스트란 자료를 나열한 형태로 저장하는 자료구조이다. 그 중에서도 연결 리스트란, 자료들이 서로 줄줄이 연결되어 있는 자료구조를 말한다. 연결 리스트는 순차 리스트와 달리 물리적 구조를 논리적 구조와 일치시킬 필요가 없기 때문에 물리적 구조가 가지고 있는 단점을 보완할 수 있다.
2. 연결 리스트의 구현
순차 리스트를 구현하기 위해서는 c에서 제공하는 포인터를 이용하면 된다. 각 자료들을 하나의 노드에 저장하고, 각 노드들에는 다음 노드의 주소값 또한 저장해야 한다. 즉, 노드를 구조체로서 정의하고, 노드 구조체의 멤버변수로는 노드에 저장될 자료를 저장하는 변수와 다음 노드의 주소값을 저장 할 포인터 변수가 필요하다. 노드가 한쪽 방향으로만 연결되어있으면 단순 연결 리스트, 양쪽 방향으로 연결되어 있다면 이중 연결 리스트라고 한다.
3. 연결 리스트의 연산
1) 삽입
연결 리스트는 노드들의 연결이 끊기지 않도록 유지해야 한다. 따라서 노드를 삽입 할 때에 삽입하는 위치에 따라 이웃 노드들과 삽입하는 노드의 링크(다음 혹은 이전 노드의 주소값을 저장하는 멤버변수)를 수정해야 한다.
단순 연결 리스트의 경우 삽입하는 위치의 전 노드의 링크를 삽입하는 노드로 하고, 삽입하는 노드의 링크를 다음 노드로 설정해주면 된다.
2) 삭제
연결 리스트의 삭제 연산 또한 삽입 연산과 마찬가지이다. 연결 리스트에서 노드를 삭제하면 그 노드의 전 노드와 다음 노드를 이어주는 작업이 필요하다. 따라서 단순 연결 리스트의 삭제할 노드의 링크를 전 노드의 링크로 설정해주면 된다.