Linked List(연결 리스트)란?
LinkedList는 데이터 구조 중 하나로, 각 데이터를 저장하는 노드(Node)들이 연결된 형태로 구성됩니다. 각 노드는 두 가지 요소를 가지고 있습니다. 하나는 실제 데이터, 다른 하나는 다음 노드를 가리키는 포인터(참조) 입니다. 이 구조는 데이터를 순차적으로 연결하는 방식으로 , 특정 상황에서 매우 유용합니다.
Linked List(연결 리스트)의 구성 요소
- 노드(Node) : 연결 리스트의 기본 단위입니다. 각 노드는 두 가지 정보를 담고 있습니다.
- 데이터(Data): 실제로 저장하고자 하는 값입니다.
- 포인터(Next):
다음 노드의 주소를 가리키는 참조입니다.
- 헤드(Head): 연결 리스트의 첫 번째 노드를 가리키는 포인터입니다. 헤드 노드는 리스트의 시작점을 나타냅니다.
- 테일(Tail): 리스트의 마지막 노드를 가리키는 포인터입니다. 테일 노드는 리스트의 끝을 나타내며, 단일 연결 리스트의 경우 이노드의 포인터는
Null이 됩니다.
단일 연결 리스트(Singly Linked List)
- 각 노드는 다음 노드만을 가리킵니다.
- 데이터를 삽입하거나 삭제할 때 간단하며, 탐색은 헤드부터 시작해
순차적으로 이루어집니다.
이중 연결 리스트 구조(Doubly Linked List)
- 각 노드는 이전 노드와 다음 노드를 모두 가리킵니다.
- 양방향으로 탐색이 가능하며, 노드를 삭제하거나 삽입할 때 유리합니다.
원형 연결 리스트(Circular Linked List)
- 마지막 노드가 첫 번째 노드를 가리키도록 연결된 리스트입니다.
- 리스트의 끝이 다시 시작으로 연결되므로, 리스트를 순환 구조로 사용할 수 있습니다.
Linked List(연결 리스트)의 장점 및 단점
장점
-
빠른 삽입과 삭제
연결 리스트에서 노드의 삽입과 삭제는 배열보다 더 효율적입니다. 배열에서는 삽입이나 삭제 후 나머지 요소들을
이동시켜야 하지만, 연결 리스트는 다음 노드의 주소를 가르키는 포인터만수정하면 되기 때문에 데이터 이동이 없어효율적입니다.특정 위치에서 삽입 또는 삭제하는 연산은
O(1)시간 복잡도를 가집니다.단, 삽입/삭제 위치를 찾는 데
O(n)시간이 필요할 수 있습니다. -
동적 크기 조절
연결 리스트는 배열과 달리 미리 크기를 정할 필요가 없습니다. 필요한 만큼 노드를 동적으로 할당하고 연결할 수 있어, 메모리를 효율적으로 사용할 수 있습니다.
단점
-
느린 탐색 속도
배열과 달리, 연결 리스트는 인덱스가 없기 때문에 특정 위치의 요소에 접근하기 위해서는 첫 노드부터 순차적으로 탐색해야 합니다. 이는
탐색 속도를 저하시킵니다.요소를 찾기 위해 전체 리스트를 탐색해야 하므로 , 최악의 경우
O(n)시간이 소요됩니다. 리스트가 길어질수록 성능에 큰 영향을 미칩니다. -
추가적인 메모리 사용
연결 리스트는 데이터 외에도 다음 노드를 가리키는 포인터를
유지해야합니다. 그렇기에 배열에 비해 더 많은 메모리를 사용합니다. 특히 이중 연결 리스트의 경우 각 노드가 두 개의 포인터(이전 , 다음 노드)를 가져야 하므로 더 많은 메모리가 필요합니다.
Linked List(연결 리스트) 구현 - Java
생활 코딩님의 강좌를 보면서 구현을 해보았습니다. 구현을 하면서 느낀점은 노드의 추가 ,삭제시 노드들의 연결을 지정해 주는것이 중요하다라는 것이었습니다.
- temp1과 temp2사이에 새로운 값을 넣고자 한다면, temp1노드의 next변수를 newNode로 지정하고 newNode의 next를 와 temp2로 지정해야 합니다. 노드들이 정상적으로 연결된다면 아래와 같이 생성이 됩니다. 이러한 과정을 구현한 코드를 적어보았습니다.
<Linked List 구현 클래스>
package Linked_list;
public class LinkedList {
private Node head; //맨 처음 노드
private Node tail; //맨 마지막 노드
private int size = 0;
//Node 클래스 : 데이터와 다음 노드의 주소를 저장할수 있어야 한다
private class Node {
private Object data; //저장할 데이터 값
private Node next; // 다음 노드를 가르킨다
public Node(Object input) {
this.data = input;
this.next = null;
}
}
//addFirst 메서드 : 최초 노드를 생성하는 메서드
public void addFirst(Object input) {
Node newNode = new Node(input);
newNode.next = head;
head = newNode;
size++;
if (head.next == null) {
tail = head;
}
}
//addLast 메서드 : 데이터가 하나 이상일때, 마지막 노드를 생성하는 메서드
public void addLast(Object input){
Node newNode = new Node(input);
if (size == 0) {
addFirst(input);
} else {
tail.next = newNode;
tail = newNode;
size++;
}
}
//노드를 탐색하는 메서드
Node node(int index) {
Node x = head;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
//노드를 인덱스 위치에 추가하는 메서드
public void add(int index, Object input) {
//맨앞에 노드를 추가하는 경우
if (index == 0) {
addFirst(input);
}else{
Node newNode = new Node(input); //새로 추가된 노드
Node temp1 = node(index - 1); //추가될 노드 인덱스 이전 위치 노드
Node temp2 = temp1.next; //추가될 노드 인덱스 다음 위치의 노드
temp1.next = newNode; //노드 연결
newNode.next = temp2; //노드 연결
}
}
//첫번쨰 노드부분을 지우는 메서드
public Object removeFirst(){
Node temp = head;
head = head.next;
Object returnData = temp.data;
temp = null;
size--;
return returnData;
}
//인덱스 위치의 노드를 삭제하는 메서드
public Object remove(int index) {
if (index == 0) {
return removeFirst();
}
Node temp = node(index - 1);
Node todoDelted = temp.next;
temp.next = temp.next.next;
Object retrunData = todoDelted.data;
if (temp.next == tail) {
tail = temp;
}
return retrunData;
}
//리스트 값을 출력하는 메서드
public String toString() {
if (head == null) {
return "[]";
}
Node temp = head;
String str = "[";
while (temp.next != null) {
str += temp.data + ", ";
temp = temp.next;
}
str += temp.data;
return str + "]";
}
}
<Main 클래스>
package Linked_list;
public class Main {
public static void main(String[] args) {
LinkedList numbers = new LinkedList();
numbers.addLast(10);
numbers.addLast(20);
numbers.addLast(30);
numbers.addFirst(5);
numbers.add(1,15);
//리스트 전체 값 출력
System.out.println(numbers);
//맨앞의 삭제된 값 출력
System.out.println(numbers.removeFirst());
//리스트 전체 값 출력
System.out.println(numbers);
//원하는 인덱스의 삭제된 값 출력 (20)
System.out.println(numbers.remove(2));
//리스트 전체 값 출력
System.out.println(numbers);
}
}
결과
도움 받은 출처 : https://www.youtube.com/watch?v=sq49IpxBl2k&list=PLuHgQVnccGMDsWOOn_P0EmAWB8DArS3Fk&index=20
