연결리스트 - 단일 연결리스트 구현 (SingleLinkedList)
public void add(int index, Object data) {
// TODO : 노드의 순서를 기준으로 해당 index에 삽입한다.
Node node = new Node();
node.data = data;
if (0 == index) {
// TODO : 맨 앞에 노드를 삽입하는 경우
node.next = head;
head = node;
} else {
// TODO : 해당 index에 삽입하려면 이전 노드를 찾아야 한다.
Node foundNode = findNode(index - 1);
node.next = foundNode.next;
foundNode.next = node;
}
++size;
}class SinglyLinkedList {
Node head = null;
int size = 0;
...
}1. 단일 연결 리스트의 Node
단일 연결 리스트의 기본 단위는 이전 시간에 설명한 대로 Node라는 단위를 사용한다.
Node는 두개의 멤버 변수인 데이터를 저장하는 Data와 다음 노드를 가리키는 참조값인 next로 구성된다.
package list;
class Node {
Node next;
Object data;
}
2. 단일 연결 리스트의 객체
2.1 단일 연결리스트의 객체의 속성은 크게 3가지로 구성된다.
1. 데이터 검색 : 원하는 데이터가 있는지 탐색하는 과정
2. 데이터 삽입 : 원하는 위치에 데이터를 삽입하는 과정
3. 데이터 삭제 : 원하는 위치에 데이터를 삭제하는 과정
3. 단일 연결 리스트 속성 구현
3.0 단일 연결 리스트의 초기화 : 현재 노드의 개수는 0 : Head → null
class SinglyLinkedList {
Node head = null;
int size = 0;
...
}
위 클래스를 간단하게 설명하자면, 첫번째 노드의 참조값을 저장하는 Node head 변수와 연결리스트의 사이즈 개수를 선언을 하면 기본 초기화가 이루어 진다.
3.1 특정 index의 Node를 찾는 방법
특정 index를 찾는 방법은 위 이미지와 같이 검색이 가능하며, 해당 과정은 아래와 같다.
1. Head값의 데이터가 찾고자 하는 데이터인지 비교한다.
2. 해당 데이터가 찾고자 하는 데이터가 아니라면, Head값의 link를 타고 다음 Node로 이동한다.
3. 해당 Node의 값이 찾고자하는 데이터인지 확인한다.
4. 만일 데이터가 아니라면 2번 과정을 시작으로 3번까지 과정을 반복하며 데이터를 찾는다.
5. 찾고자 하는 데이터가 있다면 해당값을 return하며, 그렇지 않다면 null을 return 한다.
public class SinglyLinkedList {
Node head;
int size = 0;
private Node findNode(int searchIndex) {
/**
* 찾는 노드의 index가 음수거나
* 노드의 개수보다 많거나 같으면 예외를 발생시킨다.
*/
if (0 > searchIndex || size <= searchIndex) {
throw new ArrayIndexOutOfBoundsException();
}
int nodeIndex = 0;
Node pointer = head;
/**
* 찾는 노드의 index와 노드의 순서가 동일할 때 까지
* 노드의 참조값을 이용하여 이동한다.
*/
while (nodeIndex != searchIndex) {
++nodeIndex;
pointer = pointer.next;
}
return pointer;
}
}
3.2 특정 Node를 원하는 위치에 삽입하는 방법
- 삽입하고자 하는 위치의 Node를 A라고 가정하며, 삽입하고자 하는 Node를 B라고 가정.
1. 우선 3.1 과정을 통해 원하는 A를 찾는다.
2. A의 Link값을 임시변수에 저장한다.
3. 이후 A의 Link값이 B를 가리키도록 한다.
4. 이후 B의 Link값을 임시변수의 Link값으로 저장한다.
public void add(int index, Object data) {
// TODO : 노드의 순서를 기준으로 해당 index에 삽입한다.
Node node = new Node();
node.data = data;
if (0 == index) {
// TODO : 맨 앞에 노드를 삽입하는 경우
node.next = head;
head = node;
} else {
// TODO : 해당 index에 삽입하려면 이전 노드를 찾아야 한다.
Node foundNode = findNode(index - 1);
node.next = foundNode.next;
foundNode.next = node;
}
++size;
}
3.3 특정 Node를 삭제하는 방법.
- 삭제하고자 하는 Node를 A라고 가정.
1. 우선 3.1 과정을 통해 원하는 A를 가리키는 Node를 찾는다. (B라고 가정)
2. B의 Link값을 A의 Link값으로 대체한다.
3. A의 메모리가 남아있다면 메모리를 해제한다.
public void remove(int index) {
// TODO : 해당 index에 해당하는 Node를 삭제한다.
if (0 == index && null != head) {
head = head.next;
} else {
// TODO : 삭제하려는 Node의 이전 노드
Node prevNode = findNode(index - 1);
prevNode.next = prevNode.next.next;
}
--size;
}
여기까지가, 단인연결리스트의 기본 기능에 해당하는 내용이다.