연결 리스트란?
기존의 배열을 이용한 선형 리스트의 단점을 보완한 리스트이다. 배열을 통한 리스트를 구현시, 검색은 빠르나 자료의 추가/삭제가 느린점을 보완했으나, 검색이 느린게 단점인 리스트 구현 방식이다. JAVA에서는 List인터페이스를 구현한 LinkedList라는것이 존재하며 이번 포스트에서는 직접 구현해 볼 생각이다.
연결 리스트는 배열처럼 메모리 상에 값이 연속적으로 존재하는 리스트가 아니라, 데이터와 다음 데이터의 위치를 가지고 있는 변수가 한 세트로 존재하는 구조로 이루어져 있다.
public class Node<E> {
E data;
Node<E> nextNode; // 다음 노드의 주소를 가지고 있어야 함.
}이렇게 한 세트를 Node라고 부르며, 노드의 nextNode값이 다음 노드의 주소를 가지고 있으면 되는 구조이다. 이렇게 구성하면 연속된 메모리를 활용하는 배열의 추가/삭제 처럼 오래걸리는 일이 없다.
Node처럼 데이터용 필드 data변수외에 자기 자신과 같은 클래스형의인스턴스를 참조하는 참조용 필드 nextNode를 가지는데 이런 클래스 구조를 '자기 참조(self-referential)형'이라고 한다.
참조 포스트
https://velog.io/@159jsd/ArrayList
ArrayList와 LinkedList 포스트
포인터로 연결 리스트 만들기
일단 연결 리스트의 구조를 살펴보자.
public class LinkedList<E> {
class Node<E> {
private E data;
private Node<E> next;
Node(E data, Node<E>) {
this.data = data;
this.next = next;
}
}
private Node<E> head; // 머리 포인터
private Node<E> current; // 선택 포인터
public LinkedList() {
head = current = null; // 초기에는 리스트에 아무것도 안들어 있게 됨.
}
// ... 생략
}연결리스트는 결국 앞의 노드가 뒤의 노드를 지목하고 그 지목한 노드가 또 뒤에 노드를 지목하는 구조를 가져있다.
Node1 → Node2 → Node3 → Node4 → Node5여기서 Node1을 headNode또는 머리노드라고 하고, Node5를 tailNode또는 꼬리노드라고 한다. tailNode는 가르킬 다음 노드가 없기 때문에 next(nextNode)의 값을 null로 지정해둔다. 참고로 위에서 알 수 있듯 역순으로는 참조하지 못한다.
실질적으로 LinkedList의 인스턴스가 가지는 값은 head, current변수에 저장된 다음 노드에 대한 참조주소의 정보일 뿐이다. LinkedList에 들어있는 Node가 없다면 head = null이면 되는것이고, Node가 1개라면 head.next = null이고 Node가 2개라면 head.next.next(tailNode) = null이다.
검색 메서드search()
public E search(E obj, Comparator<? super E> c) {
Node<E> ptr = head; // 현재 스캔 중인 노드
while (ptr != null) { // 검색 과정
if (c.compare(obj, ptr.data) == 0) { // 검색 성공
current = ptr;
return ptr.data;
}
ptr = ptr.next; // 이번 Node는 일치하지 않으니 다음 Node를 검사하기
}
return null; // 검색 실패
}search()는 제네릭메서드로 Comparator를 사용해서 구현한다.
매개변수 obj는 내가 검색하고자 하는 객체를 넣어주면 된다. 그럼 Comparator를 통해 obj와 현재 조사하고있는 Node의 data를 비교하고, 둘이 같다면(compare() == 0)이면 검색 성공한 것이다.
따라서 노드 스캔은 다음 조건 중 어느 하나가 성립하면 종료된다.
종료 조건1. 검색 조건을 만족하는 노드를차지 못하고 꼬리 노드를 지나가기 직전인 경우
종료 조건2. 검색 조건을 만족하는 노드를 찾은 경우
headNode앞에 노드를 삽입하는 addFirst()
public void addFirst(E obj) {
Node<E> ptr = head; // 기존의 머리 노드
head = current = new Node<E>(obj, ptr);
}addFirst()를 이용해 나머지 노드 앞에 새로운 노드를 추가하는 메서드이다. 물론 연결 리스트는 중간에도 새로운 노드를 추가할 수 있으나 이 경우는 맨 앞에 추가하는 메서드이다.
// 연결 리스트에 아무것도 없었더라면
head = current = new Node<E>(obj, null); // head에 null이들어있음만약 이 상태에서 또 addFirst()를 이용해 노드를 추가하면 위에 추가한 노드는 꼬리노드가 되며, 헤드노드는 아래처럼 바뀐다
head = current = new Node<E>(obj, 이전 헤드의 주소);이런 방식으로 앞에 한개 한개 추가된다
또 추가하면 여기 추가됨. - 새로운Head - 기존Head(현재Tail)tailNode뒤에 노드를 삽입하는 addLast()
일단 어떤 노드뒤에 노드를 삽입하려면 적어도 리스트가 비어있으면 안된다.
따라서 다음의 2가지 경우를 생각하고 메서드를 만들어야 한다.
- 리스트가 비어 있는 경우
리스트 머리에 노드를 삽입한다. 따라서 addFirst()를 호출하면 된다.- 리스트가 비어 있지 않은 경우
리스트 꼬리의 next변수에 노드 G를 참조시킨다.
public void addLast(E obj) {
if (head == null)
addFirst(obj);
else {
Node<E> ptr = head;
while (ptr.next != null) // 꼬리 노드를 찾아떠남
ptr = ptr.next;
// 꼬리 노드를 찾은 후 해당 노드의 next값에 추가할 노드 대입.
ptr.next = current = new Node<E>(obj, null); // 꼬리노드이니 next는 무조건 null이어야 함.
}
} headNode - Node2 - Node3 - Node3 - tailNode - 여기추가'여기추가'부분에 추가해야 하기에 tailNode의 next를 '여기추가'의 주소로 바꿔준다.
머리 노드 삭제 메서드 removeFirst()
public void removeFirst() {
if (head != null) // 리스트가 비어 있지 않다면,
head = current = head.next;
}LinkedList의 인스턴스 변수 head의 값을 head의다음 노드의 주소로 바꿔준다.
이러면 LinkedList에서 기존의 head값을 참조할 방법이 없기 때문에 사실상 삭제한것이나 마찬가지다.
꼬리 노드 삭제 메서드 removeLast()
꼬리 노드를 삭제하기 위해서는 리스트에 몇개의 노드가 들어있는지에 따라 다르다.
- 리스트에 노드가 1개인 경우
머리 노드를 삭제하면된다. 따라서 removeFirst()메서드를 호출한다.- 리스트에 노드가 2개이상인 경우
리스트에서 꼬리 노드F를 삭제하고 그 앞 노드의 next값을 null로 바꾼다.
public void removeLast() {
if (head != null) {
if (head.next == null)
removeFirst();
else {
Node<E> ptr = head; // 스캔 중인 노드
Node<E> pre = head; // 스캔 중인 노드의 앞 노드
while (ptr.next != null) {
pre = ptr;
ptr = ptr.next;
}
pre.next = null; // pre는 삭제 후의 꼬리 노드
current = pre;
}
}
}ptr은 꼬리노드에 도달하면 필요없어지기 때문에 꼬리노드인지 검사하는데만 사용하고 pre의 next를 null로바꾸어 ptr과의 연결을 끊어버린다. (열차 꼬리칸 끊듯이)
이렇게 어디에서도 참조(사용)되지않는 꼬리노드였던 ptr은 자바에서 가비지 컬렉터(데몬쓰레드로 구동중임)에 의해서 메모리가 자동으로 해제된다.
선택한 노드를 삭제하는 remove()
임의의 노드를 삭제하는 remove()메서드를 만들어보자. 선택한 노드가 머리노드인지 아닌지에 따라 다음과 같이 처리된다.
- 선택한 노드가 머리 노드인 경우
머리 노드를 삭제하면 된다. 따라서 removeFirst()를 호출한다.- 선택한 노드가 머리 노드가 아닌 경우
연결된 리스트에서 삭제할 노드의 앞 노드의 next 값을 삭제할 노드의 다음 노드의 주소로 바꾼다.
전자의 경우에는 이해가 쉬울것이고, 후자의 경우는 아래 간략한 설명을 보자
// 노드 4를 삭제해보자
headNode - Node1 - Node2 - Node3 - Node4 - Node5 - tailNode
headNode - Node1 - Node2 - Node3 --------- Node5 - tailNode
Node4
Node4는 어디에서도 참조되지 않게됨위처럼 Node3가 Node4를 건너뛰고 Node5를 next변수를 통해 참조하도록 바꾼다. 그럼 Node4는 어디에서도 참조할 수 없는 상태가 되고 결국 메모리가 해제된다.
// 지정 노드를 삭제한다.
public void remove(Node p) {
if (head != null) {
if (p == head) // 삭제할 p가 머리노드면
removeFirst(); // 머리 노드 삭제 메서드
else {
Node<E> ptr = head;
while (ptr.next != p) {
ptr = ptr.next;
if (ptr == null) return; // 삭제할대상이 없음
}
ptr.next = p.next;
current = ptr;
}
}
}더 많은 기능
// 선택 노드를 삭제한다.
public void removeCurrent() {
remove(current);
}
// 리스트 초기화
public void clear() {
while (head != null)
removeFirst();
current = null;
}
// 선택 노드를 하나 뒤쪽으로 진행
public boolean next() {
if (current == null || current.next == null)
return false;
current = current.next;
return true;
}삭제 관련 메서드 2개 removeCurrent, clear를 추가했고,
현재 선택한 노드의 다음 노드를 선택하는 메서드 next를 추가했다.
next는 간단히 current가 null이거나 꼬리노드가 아니면 다음으로 옮기도록 만든 메서드이다.
// 선택 노드의 데이터 출력
public void printCurrent() {
if (current == null)
System.out.println("선택한 노드가 없음");
else
System.out.println(current.data);
}
// 모든 노드를 출력
public void dump() {
Node<E> ptr = head;
while (ptr != null) {
System.out.println(ptr.data);
ptr = ptr.next;
}
}또한 현재 선택한 노드의 데이터를 출력하는 printCurrent()와, 리스트에 있는 모든 노드의 데이터를 출력하는 dump()메서드도 추가했다.
