[자료구조] 연결 리스트 (Linked List) 간단하게 알아보기

연결 리스트 (Linked List)

단방향/양방향 Linked List의 개념

단방향 Linked List 구현하기 (in Java)

---

연결 리스트 (Linked List) 

컴퓨터의 자료를 저장하는 구조의 한 종류로, 일렬로 이루어진 데이터를 저장할 때 사용한다.

Linked List 에는 배열과의 비교를 빼놓을 수가 없는데,

배열은 배열 방들이 물리적으로 한 곳에 모아져있고, 배열 방 크기를 한 번 정하면 늘리거나 줄일 수 없다.

 

노드를 삽입하는 경우,

배열로 구현을 해야한다면, 노드 한 개 추가될 때마다 배열 방을 통째로 다시 선언해서 데이터를 다시 복사하고, 추가하는 과정을 반복해야하는 반면, Linked List는 중간에 삽입하고자 하는 노드가 있을 때, 앞 노드가 가지고 있던 주소를 삽입할 노드가 갖고, 삽입할 노드의 주소를 앞 노드에게 알려주면 된다.

 

연결 리스트(Linked List)는 하나 하나 주소를 찾아가야하기 때문에 배열보다 속도가 느릴 수 있지만, 길이가 정해져있지 않은 데이터를 핸들링할 때는 Linked List가 더 편리하다.

 

 

 

단방향/양방향 Linked List의 개념

 

검색을 할 때, 노드는 앞의 노드의 주소는 알 수 없고 다음 노드의 주소만 알고 있기 때문에 언제나 앞에서 한 개씩 찾으며 검색해야한다. 이런 것을 단방향 Linked List 라고 한다.

 

반면, 양방향 Linked List는 다음 노드의 주소도 가지고 있고, 앞의 노드의 주소도 추가로 가지고 있다.

양방향 Linked List는 앞/뒤 양쪽 주소를 갖고 있기 때문에, 가장 끝의 노드를 탐색할 때, 단방향처럼 처음부터 끝까지 순서대로 탐색하지 않아도 된다. 하지만 공간의 효율성을 중요하게 생각하기 때문에 굳이 양방향을 사용하지 않는다.

 

 

 

단방향 Linked List 구현하기 (in Java)

class Node {
	int data;
	Node next = null;
	
	Node(int d) {
		this.data = d;
	}
	
	void append(int d) {
		Node end = new Node(d);
		Node n = this;
		while(n.next != null) {
			n = n.next;
		}
		n.next = end;
	}

	void delete(int d) {
		Node n = this;
		while(n.next != null) {
			if(n.next.data == d) {
				n.next = n.next.next;
			} else {
				n = n.next;
			}
		}
	}

	// node 출력
    void retrieve() {
        Node n = this;
        while (n.next != null) {
            System.out.print(n.data + "-> ");
            n = n.next;
        }
        System.out.println(n.data);
    }
}

public class SingleLinkedList {
    public static void main(String[] args) {
		Node head = new Node(1);
		head.append(2);
		head.append(3);
		head.append(4);
		head.retrieve();
		head.delete(2);
		head.retrieve();
	}
}