상위문서 : 자료구조
필수참고문서 : 빅오표기법 , 배열리스트
목차
1. 개요
2. 설명
3. 배열리스트와 비교
4. 구현
4.1. JAVA로 구현
4.2. C#으로 구현
4.2. C#으로 구현
1.개요
연결리스트는 노드를 이용하여 리스트의 추상형 자료구조(ADT)를 구현한 것이다. 리스트(ADT)는 다음과 같은 연산을 가지고 있다.
- 빈 리스트(노드)를 생성(생성자를 이용)
- 리스트가 비어있는지 확인(isEmpty)
- 리스트에 원소를 삽입(add), 리스트 맨 앞에 삽입(add first), 리스트 맨 뒤에 삽입(add last)
- 리스트의 특정 원소를 보는(toString)
- 특정 리스트 삭제(remove), 리스트 맨 앞 삭제(remove first), 리스트 맨 뒤 삭제(remove last)
2.설명
연결리스트를 이해하기 위해서 위의 그림을 다시보자 저 위에서 회색 박스를 노드(Node)라고 하며 노드 안에는 두가지의 데이터가 담겨있다. 하나는 그 노드 안에 담겨있는 데이터와 다른 하나는 그 노드의 다음 데이터를 지칭하는 주소의 정보가 담겨있는 것이다.
이로 인해 연결리스트는 배열리스트와는 다른 성질이 있는데 그것은 노드 안에 다음 노드 주소를 바꾸면 쉽게 새로운 노드를 추가하거나 기존 노드를 삭제할 수 있다는 것이다. 또한 배열리스트는 처음 선언한 크기만큼만 사용이 가능한데(늘리는 방법이 있지만 연결리스트에 비하여 매우 비효율적이다.) 연결리스트는 컴퓨터의 메모리 용량만 따라준다면 무한이 만들 수 있다는 것이다.
3.배열리스트와 비교
연결리스트는 배열리스트와 trade-off가 있다. 즉 어떤 부분은 안좋고 어떤 부분은 좋은데 그것이 배열리스트와 상반된 관계라는 것이다.
다음표를 보자
다음표를 보자
| 연결리스트 | 배열리스트 | |
| 처음 부분 값 추가 및 삭제(add first,remove first) | O(1) | O(n) |
| 마지막 부분 값 추가 및 삭제(add last, remove last) | O(n) | O(1) |
| 값 추가 및 삭제(add,remove) | O(n) | O(n) |
| 특정 값 찾기(toString) | O(n) | O(1) |
| 노드나 배열 첫번째가 비어있는지 확인(isEmpty) | O(1) | O(1) |
4.구현
일단 add 부분을 구현할 때를 생각해보자. add의 종류는 3종류가 있는데 각각의 구현은 다음과 같이한다.
필자의 방식이 무조건 정답이 아니니 직접 생각해보며 짜보자 필자의 방식은 이렇다.
◎ addfist 구현
◎addlast 구현
◎add 구현(무조건 head와 tail 노드를 제외한 노드가 있어야됨)
◎tostring 구현
◎removefirst 구현
◎removelast 구현
필자의 방식이 무조건 정답이 아니니 직접 생각해보며 짜보자 필자의 방식은 이렇다.
◎ addfist 구현
- head 노드를 임시 노드를 만들어 임시노드에 저장한다.
- 새 노드를 head 노드에 넣는다.
- head노드의 다음 주소값을 임시노드에 저장되어 있던 다음 주소값으로 설정한다.
- 만약 tail 노드의 값이 비어있으면 tail 노드의 값을 head 노드와 일치시킨다.
◎addlast 구현
- 만약 head 노드의 값이 비어있으면 addfirst를 수행한다.
- 그게 아니라면 tail노드를 임시 노드를 만들어 임시노드에 저장한다.
- 임시 노드의 다음 주소값을 새 노드의 주소로 지정
- tail 노드에는 새 노드를 넣는다.
◎add 구현(무조건 head와 tail 노드를 제외한 노드가 있어야됨)
- 만약 head 노드의 값이 비어있으면 addfirst를 수행한다.
- 그게 아니라면 임시노드에 head를 넣는다.
- 만약 새 노드를 넣을 인덱스가 x번(x는 0이 아닌 자연수)이라면 임시노드에 다음 노드의 주소를 이용해 값을 넣는것을 x번 반복한다.
- 임시노드의 다음노드 주소값을 새로운 노드의 다음노드 주소값에 넣는다.
- 임시노드의 다음 노드 주소값을 새로운 노드의 주소값으로 넣는다.
◎tostring 구현
- 임시 노드를 만들고 그 노드에 head를 넣는다.
- 그리고 찾는 인덱스 x번 만큼 다음 노드 주소로 이동한다.
- 그 다음 노드의 있는 데이터를 리턴한다.
◎removefirst 구현
- 임시 노드를 만들고 head 노드를 넣는다.
- head노드에는 임시노드의 다음 노드 주소값을 이용하여 임시노드의 다음 노드를 넣는다.
- 임시노드를 삭제(갈비지 컬렉터나 메모리 해제 갈비지 컬렉터는 임시노드의 다음 주소값을 null로 만들면 작동한다.)
- 만약 전체 연결리스트의 사이즈가 0 즉 isEmpty라면 tail 노드에 head 노드를 넣는다.
◎removelast 구현
- 임시 노드를 만들고 head 노드를 넣는다.
- 임시 노드에 있는 다음 노드의 주소값을 이용하여 다시 임시노드에 넣는다. 이것을 전체 연결리스트 사이즈만큼 반복한다.
- 임시노드를 삭제(갈비지 컬렉터나 메모리 해제 갈비지 컬렉터는 임시노드의 다음 주소값을 null로 만들면 작동한다.)
- 만약 전체 연결리스트의 사이즈가 0 즉 isEmpty라면 tail 노드에 head 노드를 넣는다.
