Linked List 링크드 리스트(연결리스트)_단순연결리스트

Linked List 링크드 리스트(연결리스트)

연결리스트는 노드와 링크로 구성이 된다. 

노드 : 실제의 정보를 담고 있는 하나의 단위

링크 : 인접 노드의 위치를 저장하고 있어 연결 리스트의 순서를 유지할 수 있게 하는 연결 고리

배열과 차이점

-배열과는 다르게 동적인 자료구조 => 메모리절약

배열은 여분의 공간을 마련해야 하지만 연결리스트는 필요할 때만 메모리를 할당 할 수 있다.

-배열은 연속된 공간을 차지 하는데, 연결리스트는 동적으로 수시로 할당 해제 되기 때문에 메모리의 연속된 공간을 차지하지 못한다. 순서도 제대로 되어 있지 않다.(이런 연결 리스트의 순서를 유지시켜 주는 것은 링크(Link)에 의해서 가능해진다.)

-자료 순서의 재배열이 편하다. (링크가 가리키는 방향만 바꿔주면 된다) 

연결리스트 종류

단순연결리스트

단순 연결 리스트는 정보를 저장하는 노드와 바로 다음의 노드를 가리키는 링크 하나로 구성 되어 있다.

제일 처음의 노드는 누가 가리켜 줄 것인가라는 문제 때문에 사용자에게 알려진 연결 리스트의 입구인 머리가 필요하다. 이 머리는 일반적으로 전역 변수로 선언이 되어 모듈 내의 어떤 부분에서도 접근 가능하도록 개방되어 있고, 소멸되지 않는다. 그리고 연결리스트의 제일 마지막 노드는 항상 무엇인가를 가리켜야 하는데 특별히 마지막을 나타내는 꼬리 노드를 만들어서 마지막 노드임을 표시하게 한다.

스택기반 노드 구현 연습

Node클래스 

연결리스트 초기화

노드 삽입

노드 삭제

원하는 노드 찾기

학습참고 : 

1) c로배우는 알고리즘_이재규

2) http://egloos.zum.com/sun77/v/335278