자료구조 & 알고리즘/자료구조
LinkedList
maeng0830
2023. 5. 12. 23:07
ArrayList는 크기를 변경할 수 없고(사실 저장 공간은 크기가 정적인 배열이며, 저장 공간이 부족할 경우 새로 배열을 생성한다), 시작 또는 중간 데이터의 추가/삭제 시 속도면에서 비효율적이라는 단점이 있다.
LinkedList는 ArrayList의 단점을 보완한 자료구조이다.
LinkedList의 특징
LinkedList는 특정한 저장 공간에 데이터를 저장하지 않는다. 노드(Node)라는 객체를 통해 데이터를 저장한다.
- 노드는 데이터와 다음 노드에 대한 참조로 구성되어있다.
- 다음 노드에 대한 참조를 통해 노드들은 연결된다.
- 첫 번째 노드를 head, 마지막 노드를 tail이라고 부른다. 노드가 1개일 경우, head와 tail은 동일한 노드이다.
- LinkedList 객체는 첫 번째 노드를 참조하는 head, 마지막 노드를 참조하는 tail을 갖고 있으며, 해당 참조를 통해 LinkedList에 저장된 데이터들에 접근한다.
LinkedList의 데이터 조작
LinkedList의 데이터 추가 과정
- 새로운 노드(newNode)를 추가하려는 인덱스의 이전 노드(prevNode)가 새로운 노드(newNode)를 참조하도록 변경한다.
- newNode가 prevNode의 기존 다음 노드(nextNode)를 참조하도록 변경한다.
LinkedList의 데이터 삭제 과정
- 삭제하려는 노드(removeNode)의 이전 노드(prevNode)가 삭제하려는 노드(removeNode)의 다음 노드(nextNode)를 참조하도록 변경한다.
LinkedList의 장단점
장점
- 시작 또는 중간 데이터를 추가/삭제할 때도 인접한 노드와의 연결 작업만 실행해주면 되므로 비교적 속도가 빠르다.
단점
- LinkedList의 노드들은 메모리 상에 연속적으로 존재하지 않는다. 따라서 n번째 노드에 접근하기 위해서는 참조를 통해 n번째 노드까지 순차적으로 접근해야한다. 따라서 데이터가 많을 수록 검색의 효율이 떨어지게 된다.
LinkedList 구현
아래는 LinkedList를 실제로 구현한 코드이다.
주석을 참고하여 LinkedList의 동작을 이해해보자.
Node 구현부
public class Node<T> {
T data; // 데이터
Node<T> next; // 다음 노드에 대한 참조
public Node(T data) {
this.data = data;
}
}
LinkedList 구현부
public class LinkedList<T> {
private Node<T> head; // 첫 번째 노드에 대한 참조
private Node<T> tail; // 마지막 노드에 대한 참조
private int size; // 저장된 데이터 개수(= head ~ tail 노드 개수)
// LinkedList 생성자
// 아직 노드가 없으므로 head, tail은 null, size는 0이다.
public LinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
// 목표 인덱스의 노드를 반환하는 메소드
private Node<T> search(int index) {
// 목표 인덱스의 값이 가능한 범위의 값인지 확인한다.
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node<T> x = head;
// 목표 인덱스만큼 순차적으로 접근한다.
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
// 맨 앞에 데이터를 저장하는 메소드
public boolean addFirst(T data) {
// 새로운 데이터를 갖는 노드 새로운 생성
Node<T> newNode = new Node<>(data);
// 새로운 노드는 첫 번째에 위치할 것이므로, 새로운 노드는 기존의 head를 참조한다.
newNode.next = head;
// 새로운 노드를 head로 지정
head = newNode;
size++;
// head의 다음 노드가 null이라는 것은 노드가 1개라는 의미
if (head.next == null) {
// tail을 head와 동일한 노드로 지정
tail = head;
}
return true;
}
// 맨 끝에 데이터를 저장하는 메소드
public boolean addLast(T data) {
// 기존에 데이터가 없을 경우, 맨 앞에 저장하는 것과 동일한 의미이다.
if (size == 0) {
return addFirst(data);
}
// 기존에 데이터가 있는 경우, 따로 구현부를 작성한다.
// 새로운 데이터를 갖는 새로운 노드를 생성한다.
Node<T> newNode = new Node<>(data);
// 기존의 마지막 노드가 새로운 노드를 참조하도록 지정한다.
tail.next = newNode;
// 새로운 노드를 tail로 지정한다.
tail = newNode;
size++;
return true;
}
// 기본적인 데이터 저장 메소드
public boolean add(T data) {
// 기본적으로 맨 끝에 데이터를 저장하므로, addLast(...)를 호출한다.
return addLast(data);
}
// 목표 인덱스에 데이터를 저장하는 메소드
public boolean add(int index, T data) {
// 목표 인덱스의 값이 가능한 범위의 값인지 확인
if (index > size || index < 0) {
throw new IndexOutOfBoundsException();
}
// 맨 앞에 데이를 추가하는 경우
if (index == 0) {
return addFirst(data);
}
// 맨 끝에 데이터를 추가하는 경우
if (index == size) {
return addLast(data);
}
// 중간에 데이터를 추가하는 경우
Node<T> prevNode = search(index - 1); // 목표 인덱스 이전의 노드(prevNode)
Node<T> nextNode = prevNode.next; // prevNode의 기존 다음 노드(nextNode)
Node<T> newNode = new Node<>(data); // 새로 추가할 노드(newNode)
prevNode.next = newNode; // prevNode가 newNode를 참조하도록 변경
newNode.next = nextNode; // newNode가 nextNode를 참조하도록 변경
size++;
return true;
}
// 기본적인 데이터 삭제 메소드
// 맨 앞의 데이터 삭제
public boolean remove() {
// 저장된 데이터가 존재하는 지 확인
if (head == null) {
throw new NoSuchElementException();
}
// head를 head의 다음 노드로 변경
// 기존의 head가 유일한 노드였을 경우, null로 변경되는 것
head = head.next;
size--;
// 저장된 데이터가 없는 경우, tail도 null로 변경
if (size == 0) {
tail = null;
}
return true;
}
// 목표 인덱스 데이터 삭제 메소드
public boolean remove(int index) {
// 목표 인덱스가 가능한 범위의 인덱스인지 확인
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException();
}
// 맨 앞의 데이터를 삭제하는 경우
if (index == 0) {
return remove();
}
// 그렇지 않는 경우
Node<T> prevNode = search(index - 1); // 목표 인덱스의 이전 노드(prevNode)
Node<T> removeNode = prevNode.next; // 목표 인덱스의 노드(removeNode)
Node<T> nextNode = removeNode.next; // removeNode의 다음 노드(nextNode)
prevNode.next = nextNode; // prevNode가 nextNode를 참조하도록 변경
// prevNode가 마지막 노드일 경우, tail로 지정
if (prevNode.next == null) {
tail = prevNode;
}
size--;
return true;
}
// 목표 데이터 삭제 메소드
public boolean remove(T data) {
Node<T> prevNode = head;
Node<T> x = head;
// head부터 순차적으로 참조하면서 목표 데이터를 갖는 노드를 찾는다.
for (; x != null; x = x.next) {
if (data.equals(x.data)) {
// 찾을 경우 정지
break;
}
prevNode = x;
}
if (x == null) { // 목표 데이터를 가진 노드가 없는 경우
return false;
} else if (x.equals(head)) { // 목표 데이터를 가진 노드가 head인 경우
return remove();
} else { // 목표 데이터를 가진 노드가 중간 ~ 마지막 노드인 경우
prevNode.next = x.next;
if (prevNode.next == null) {
tail = prevNode;
}
size--;
return true;
}
}
// 목표 인덱스의 데이터 반환 메소드
public T get(int index) {
return search(index).data;
}
// 목표 인덱스의 데이터 변경 메소드
public void set(int index, T data) {
Node<T> targetNode = search(index);
targetNode.data = data;
}
// 목표 데이터의 인데스 반환 메소드
public int indexOf(T data) {
int index = 0;
// head ~ tail까지 순차적으로 참조하면서, 노드의 데이터가 목표 데이터와 일치하는지 확인
for (Node<T> x = head; x != null; x = x.next) {
if (data.equals(x.data)) {
// 노드의 데이터와 목표 데이터가 일치할 경우 해당 인덱스 반환
return index;
}
index++;
}
// 목표 데이터를 가진 노드가 없을 경우 -1 반환
return -1;
}
// 목표 데이터가 저장되어있는지 확인하는 메소드
public boolean contains(T data) {
return indexOf(data) >= 0;
}
// 저장된 데이터 존재 여부를 확인하는 메소드
public boolean isEmpty() {
return size == 0;
}
// 저장된 데이터의 개수를 반환하는 메소드
public int size() {
return size;
}
// LinkedList에 저장된 모든 데이터를 삭제하는 메소드
public void clear() {
// head ~ tail까지 순차적으로 참조하며 데이터를 제거한다.
for(Node<T> x = head; x != null;) {
Node<T> nextNode = x.next;
x.data = null;
x.next = null;
x = nextNode;
}
// head, tail, size를 초기 값으로 변경한다.
head = null;
tail = null;
size = 0;
}
// toString() 오버라이딩
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
for (Node<T> x = head; x != null; x = x.next) {
stringBuilder.append(" ").append(x.data);
}
stringBuilder.append(" ]");
return stringBuilder.toString();
}
}
사용 예시
public class Main {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 10; i++) {
list.add(i + 1);
}
System.out.println("list = " + list);
// list = [ 1 2 3 4 5 6 7 8 9 10 ]
////////////////////////////////////////////////////////////////////////////////////
for (int i = 0; i < 10; i++) {
list.add(i, (i + 1) * 100);
}
System.out.println("list = " + list);
// list = [ 100 200 300 400 500 600 700 800 900 1000 1 2 3 4 5 6 7 8 9 10 ]
////////////////////////////////////////////////////////////////////////////////////
list.remove(0);
list.remove(Integer.valueOf(1));
System.out.println("list = " + list);
// list = [ 200 300 400 500 600 700 800 900 1000 2 3 4 5 6 7 8 9 10 ]
////////////////////////////////////////////////////////////////////////////////////
System.out.println("list.contains(1000) = " + list.contains(1000));
// true
System.out.println("list.contains(100) = " + list.contains(100));
// false
////////////////////////////////////////////////////////////////////////////////////
System.out.println("list.indexOf(200) = " + list.indexOf(200));
// 0
System.out.println("list.lastIndexOf(10) = " + list.indexOf(10));
// 17
////////////////////////////////////////////////////////////////////////////////////
System.out.println("list.isEmpty() = " + list.isEmpty());
// false
list.clear();
System.out.println("list.isEmpty() = " + list.isEmpty());
// true
}
}