[자료구조] 연결리스트(LinkedList) 개념

배열과 연결리스트 비교

배열과 연결리스트의 비교

 

배열은 생성하는 시점에 반드시 배열의 크기를 지정해줘야 하고 생성한 후에는 그 크기를 변경할 수 없다.

즉 삽입연산이나 삭제연산 후에 연속적인 물리 주소를 유지하기 위해서 원소들을 이동시키는 추가적인 작업과 시간이 소요된다.

 

연결리스트는 배열처럼 데이터 집합 보관 기능을 가지면서도 배열과 달리 유연하게 크기를 바꿀 수 있다.

자료의 논리적인 순서와 물리적인 순서가 일치X -> 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 방식으로 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않는다.

 

연결리스트

연결리스트는 리스트를 연결 자료구조로 표현한 구조이다.

연결하는 방식에 따라 단순 연결 리스트와 원형 연결 리스트, 이중 연결 리스트, 이중 원형 연결 리스트로 분류된다.

 

단순 연결 리스트

연결리스트는 노드를 연결해서 만든 리스트라고 해서 붙여진 이름이다.

단순 연결 리스트는 노드가 한방향으로만 연결된 구조를 가진다.

 

노드

노드의 구조

 

원소의 값을 저장하는 데이터 필드와 다음 노드의 주소를 저장하는 링크필드로 구성되어 있다.

 

struct Node
{
    int data; 
    struct Node* link; 
};

노드는 다음과 같은 구조체로 나타낼 수 있다. 

struct Node MyNode;

typedef struct node
{
    int data;
    struct node* link;
}Node;

Node MyNode;

별칭을 이용하여 선언된 구조체는 선언 시에 다음과 같이 간편하게 인스턴스를 만들 수 있다.