C언어 :: 연결리스트 ( Linked List ), 링크드리스트

1. 연결리스트(Linked List)란?

 연결 리스트의 사전적 의미는

연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

[출처] [C언어] - 링크드 리스트 (Linked List)|작성자 테리

 연결리스트란 각 노드에 데이터와 링크를 가지고 마치 비엔나 소세지 처럼 한줄로 연결되어 있는 데이터 저장 방식이다.

[출처] 자료구조 - 링크드 리스트(Linked List)|작성자 임종수

2. 연결리스트의 쓰임(용도)

배열과 연결리스트의 차이점

-배열의 특성은 메모리공간에서 연속이라는 점이다. 그래서 첨자연산으로 빠른 속도가 보장되지만, 메모리가 연속이어야하기 때문에, 삽입과 삭제가 번거롭다. 하지만 연결리스트는 메모리상에 연속이지 않아도 된다. 왜냐하면 다음데이터에 대한 링크정보를 지니고 있기 때문이다.

연결리스트의 장점과 단점

-장점 : 배열과는 다르게 맨처음 선언시 데이터의 길이를 몰라도 사용이 가능하고 노드(자료)의 추가, 삽입, 삭제가 매우 용이하다. 노드가 추가될 때 마다 메모리 동적할당을 함으로써 메모리공간을 낭비하지 않는다.

-단점 : 배열과 달리 각 노드에 Index가 주어지지 않아서 탐색할때 처음(head)부터 탐색해야 됨으로 속도가 느리다. 따라서 특정 위치의 요소접근이 힘들다.

용도(사용처)

-조회는 드물고 추가, 삽입, 삭제가 잦은곳에서 자주 사용 된다.

ex) 반 아이들의 정보를 출석번호로 나열(추가, 삭제)

3. 연결리스트의 구조 및 구현

-구조

[그림 7-12] 연결 리스트의 예

[네이버 지식백과]연결 리스트 (컴퓨터 개론, 2013.3.10, 한빛아카데미(주))

-구현예제

-결과

+) 스택 리스트

-결과