[자바 자료구조] 링크드 리스트

개념

 배열과 비교 

 링크드 리스트는 노드를 기반으로 한 선형자료구조이다. 자료구조 중에서 선형자료구조로 가장 많이 쓰이는 것은 배열일 것이다. 그러면 왜 배열을 사용하지 않고 링크드리스트를 쓰는걸까?

 

 그 이유는 배열을 정의할 때의 코드를 보면 알 수 있다. 배열을 선언할 때(자바기준)는 크게 2가지 방법이있다. 첫번째는 배열을 선언한 다음 인덱스로 접근하여 초기화 하는 방법이 있고, 

int[] array1 = new int[5];
array1[0]=1;
array1[1]=2;
array1[3]=3;
array1[4]=4;

 두번째는 선언과 동시에 초기화를 하는 방법이다

int[] array2 = {1,2,3,4,5};

이 두 방법의 공통점은 모두 사용할 배열의 공간을 미리 할당을 해야한다는 것이다. 이미 생성된 array1, array2에 6을 추가하려면 크기가 6인 배열을 새로 생성해야 한다. 이러한 불편함을 해결해 주는 것이 링크드 리스트이다. 

 

구조

 그러면 어떻게 "배열의 크기를 고려하지 않아도 된다"는 문제를 해결할까? 배열의 경우 메모리에 저장될 때 연속된 메모리에 할당된다. 따라서 배열의 0번째 요소의 주소만 알면 이후 요소의 주소는 자료형의 크기만큼을 더해 구할 수 있으므로 인덱스 번호로 바로 접근이 가능했다. 다시말해 접근하고자 하는 배열의 이전, 이후 요소의 주소를 알 필요 없이 인덱스 번호만 알면 접근이 가능하다. 

 배열은 위처럼 연속된 공간을 할당해야하기 때문에 배열의 크기를 미리 알아야 한다. 그러면 "배열의 크기를 미리 알아햐 한다"는 문제를 해결하기 위해 연속된 공간을 할당하지 않고 배열을 선언 하면 되지 않을까? 새로운 요소가 추가될 때 메모리의 빈공간에 임의로 할당을 해주는 방법으로 배열을 만들어가면 배열 크기의 제약없이 배열을 사용할 수 있을 것이다. 

 

이제 각 요소를 연결해주면 링크드 리스트의 구조가 완성된다. 

 새로운 요소를 추가할 때는 임의의 공간에 요소를 생성하고, 배열의 맨 마지막 요소와 연결을 해주면 된다. 

 

노드

 위의 그림을 보면 두개의 데이터를 저장할 변수가 필요하다는 걸 알 수 있다. 하나는 배열의 요소값이고 다른 하나는 현재 요소와 연결된 다음 요소의 주소이다. 하나의 요소를 생성할 때 배열의 데이터와, 다음 요소의 주소값을 저장하는 2개의 변수가 필요하다. 이를 위해 노드를 사용한다. 

class Node<E> {
	E data;
        Node<E> next;
}

 이제 1,2,3,4,5를 링크드 리스트로 구현해보자. 순서는 노드를 생성하고, 각 노드를 순서에 맞게 연결해 주면 된다. 

class Node<E>{
	E data;
	Node<E> next;
	
	public Node(E data, Node<E> next) {
		this.data = data;
		this.next = next;
	}
    //getter, setter생략
}
public class LinkedListDemo{
		public static void main(String[] args) {
		
		//노드 생성
		Node<Integer> node1 = new Node<Integer>(1,null);
		Node<Integer> node2 = new Node<Integer>(2, null);
		Node<Integer> node3 = new Node<Integer>(3, null);
		Node<Integer> node4 = new Node<Integer>(4, null);
		Node<Integer> node5 = new Node<Integer>(5, null);
		
		//순서에 맞게 노드 연결
		node1.setNext(node2);
		node2.setNext(node3);
		node3.setNext(node4);
		node4.setNext(node5);
	}

}

 

 

 

구현

링크드리스트의 연산을 구현해보자. 그러기 위해 노드를 링크드 리스트의 인스턴스 내부클래스로 선언하고 연산들을 멤버메서드로 구현하면 된다. 여기서 주의해야 할 점은 반드시 head를 명시해야 한다는 것이다. 링크드리스트에는 인덱스가 없기 때문에 특정노드에 접근하기 위해서는 첫번째 노드를 알아야 한다. 

 

class LinkedList<E> {
	class Node<E> {
		E data;
		Node<E> next;

		public Node(E data, Node<E> next) {
			this.data = data;
			this.next = next;
		}
	}
	Node<E> head;
	public LinkedList() {
		head = null;
	}

}

검색

 현재노드의 데이터와 매개변수로 넘어온 데이터가 같으면 현재노드의 인덱스를 반환하고, 같지 않으면 다음노드로 이동한다. 

	public int search(E obj) {
		Node<E> ptr = head;
		int currentIndex =0;
		
		while(ptr!=null) {
			if((ptr.data).equals(obj)) {
				return currentIndex;
			}
			ptr = ptr.next;
			currentIndex ++;
		}
		return -1;
	}

 

삽입

삽입하고자 하는 index에 데이터를 삽입하는 메서드다.  3가지 경우의 수가 있다. 맨 처음에 삽입하는 경우, 중간에 삽입하는 경우, 마지막에 삽입하는 경우이다. 맨 처음에 삽입하는 경우를 따로 경우의 수로 뺀 이유는, 맨 처음에 삽입하게 되면 head가 바뀌기 때문이다. 따라서 index ==0 인경우와 그 외 경우로 나눠서 메서드를 구현해야한다. 

 

1) index ==0일때

next가 현재 head인 노드를 생성한다. 

head에 새로 생성한 노드를 할당한다. 

 

2) 그외 

 

 

public void add(int index, E obj) {
		if(head == null) {
			head = new Node<E>(obj,null);
		}
		if(index == 0) {
			head = new Node<E>(obj, head);
		}
		else {
			Node<E> ptr = head;
			int currentIndex = 0;
			while(currentIndex!=index-1) {
				currentIndex ++;
				ptr = ptr.next; 
			}
			Node<E> node = new Node<E>(obj,ptr.next);
			ptr.next = node;
		}
	}

 

삭제

삭제하고자 하는 index가 주어졌을때, index의 바로 전 노드를 찾아서 index-1 노드의 next를 index노드의 next로 설정해준다. 이때 index가 0일 경우, 즉 head를 삭제하는 경우는 head에 head의 다음노드를 할당한다. 

	public void remove(int index) {
		if(head== null) {
			System.out.println("삭제할 노드가 없습니다.");
		}
		if(index == 0) {
			head = head.next;
		}
		else {
			int i = 0;
			Node<E>ptr = head;
			
			while(i<index-1) {
				i++;
				ptr = ptr.next;
			}
			ptr.next = ptr.next.next;
		}
	}

 

시간복잡도