[자료구조] LinkedList 개념과 Java 구현 & 사용법 예제

LinkedList란

각 노드가 데이터(Data field)와 포인터(Link field)를 가지고 한 줄로 연결되어 있는 방식의 자료구조이다. 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당한다. 

 

장점

삭제, 삽입해야 할 경우 노드의 링크를 끊거나 연결하면 되기 때문에 효율적이다.

단점

요소를 검색해야 하는 경우 첫 노드(HEAD)부터 찾으려는 노드가 나올 때까지 연결된 노드들을 모두 찾아봐야 하기 때문에 성능이 떨어진다.

 

ArrayList와의 차이점

1. 데이터를 삽입할 때 ArrayList는 인덱스의 값을 당기거나 미는 행위를 해야 하지만 노드는 링크를 끊고 연결하면 되기 때문에 속도가 빠르다.

2. ArrayList는 Random Access가 가능하기 때문에 각각의 인덱스를 거치지 않고 원하는 인덱스를 바로 찾아갈 수 있지만 LinkedList는 반드시 HEAD를 거쳐서 원하는 노드를 찾아야 한다.

3. ArrayList는 배열의 사이즈를 정해놓고 사용하고 단방향의 LinkedList는 한계가 없다. 하지만 java 내부에서는 데이터를 삽입할 때 배열의 사이즈가 넘어서면 사이즈를 알아서 늘려주고 데이터를 옮겨주기 때문에 실제로 이 특성이 드러나진 않는다. 이러한 형태의 구현 형태를 Dynamic Array라고 한다.

 

 

Java로 구현해보기

1. 객체 생성

public Class LinkedList {
	private Node head;
    private Node tail;
    private int size = 0;
    
    private class Node {
    	private Object data;
        private Node next;
        public Node(Object input) {
        	this.data = input;
            this.next = null;
        }
        public String toString() {
        	return String.valueOf(this.data);
        }
    }
}

public class Main {
	public static void main(String[] args) {
    	LinkedList numbers = new LinkedList();
    }
}

 

2. addFirst(Object input) : HEAD에 노드 추가

public class Main {
	public static void main(String[] args) {
    	LinkedList numbers = new LinkedList();
        numbers.addFirst(30);
        numbers.addFirst(20);
        numbers.addFirst(10);
    }
}

public class LinkedList {
	...
    public void addFirst(Object input) {
    	Node newNode = new Node(input);
        newNode.next = head;
        head = newNode;
        size++;
        if (head.next == null) {
        	tail = head;
        }
    }
}

 

 

3. addLast(Object input) : 마지막에 노드 추가

public class Main {
	public static void main(String[] args) {
    	LinkedList numbers = new LinkedList();
        ...
        numbers.addLast(10);
        numbers.addLast(20);
        numbers.addLast(30);
    }
}

public class LinkedList {
	...
    public void addLast(Object input) {
    	Node newNode = new Node(input);
        if (size == 0) {
        	addFirst(input);
        } else {
        	tail.next = newNode;
            tail = newNode;
            size++;
        }
    }
}

 

4. node(int index) : 원하는 인덱스에 있는 노드 찾기

public class Main {
	public static void main(String[] args) {
    	LinkedList numbers = new LinkedList();
        numbers.addLast(10);
        numbers.addLast(20);
        numbers.addLast(30);
    }
}

public class LinkedList {
	...
    Node node(int index) {
    	Node x = head;
        for(int i = 0; i < index; i++) {
        	x = x.next;
        }
        return x;
    }
}

 

5. add(int index, Object input) : 5번 메소드를 이용해서 노드 추가하기

public class Main {
	public static void main(String[] args) {
    	LinkedList numbers = new LinkedList();
        numbers.addLast(10);
        numbers.addLast(20);
        numbers.addLast(30);
        numbers.add(2, 25); // index 2 자리에 25 값을 가진 노드 추가
    }
}

public class LinkedList {
	...
    public void add(int k, Object input) {
    	if (k == 0) {
        	addFirst(input);
        } else {
        	Node temp1 = node(k-1);
            Node temp2 = temp1.next;
            Node newNode = new Node(input);
            temp1.next = newNode;
            newNode.next = temp2;
            size++;
            if (newNode.next == null) {
            	tail = newNode;
            }
        }
    }
}

 

6. toString() : 출력문

public class Main {
	public static void main(String[] args) {
    	LinkedList numbers = new LinkedList();
        numbers.addLast(10);
        numbers.addLast(20);
        numbers.addLast(30);
        System.out.println(numbers);
    }
}

public class LinkedList {
	...
    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 + "]";
    }
}

 

7. removeFirst()

public class LinkedList {
	...
    public Object removeFirst() {
        Node temp = head;
        head = head.next;
        Object returnData = temp.data;
        temp = null;
        return returnData;
	}	
}

 

 

8. remove(int index), removeLast()

public class LinkedList {
	...
    public Object remove(int k) {
       	if (k == 0) {
        	return removeFirst();
        }
        Node temp = node(k-1);
        Node todoDeleted = temp.next;
        temp.next = temp.next.next;
        Object returnData = todoDeleted.data;
        if (todoDeleted == tail) {
        	tail = temp;
        }
        todoDeleted = null;
        size--;
        return returnData;
	}
    public Object removeLast(int k) {
       	return remove(size-1);
	}
}

 

9. size(), get(int index)

public class LinkedList {
	...
    public int size() {
    	return size;
    }
    public Object get(int k) {
    	Node temp = node(k);
        return temp.data;
    }  	
}

 

10. indexOf(Object data) : 원하는 데이터를 가진 노드의 인덱스 값 구하기

public class LinkedList {
	...
    public int indexOf(Object data) {
    	Node temp = head;
        int index = 0;
        while(temp.data != data) {
        	temp = temp.next;
            index++;
            if (temp == null) {
            	return -1;
            }
        }
        return index;
    }
}

 

11. Iterator next

public class Main {
	public static void main(String[] args) {
    	LinkedList numbers = new LinkedList();
        numbers.addLast(10);
        numbers.addLast(20);
        numbers.addLast(30);
        LinkedList.ListIterator i = numbers.listIterator();
        System.out.println(i.next());
    }
}

public class LinkedList {
	...
    public ListIterator listIterator() {
    	return new ListIterator();
    }
    public class ListIterator {
    	
        private Node next;
        private Node lastReturned;
        private int nextIndex++;
    
    	ListIterator() {
        	next = head;
        }
    	public Object next() {
        	lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.data;
        }
    }
}

 

12. Iterator hasNext

public class Main {
	public static void main(String[] args) {
    	LinkedList numbers = new LinkedList();
        numbers.addLast(10);
        numbers.addLast(20);
        numbers.addLast(30);
        LinkedList.ListIterator i = numbers.listIterator();
        while(i.hasNext()) {
        	System.out.println(i.next());
        }
    }
}

public class LinkedList {
	...
    public boolean hasNext() {
    	return nextIndex < size();
    }
}

 

LinkedList 사용법

LinkedList 선언

 // 타입 미설정, Object로 선언된다.
LinkedList list = new LinkedList();
// 타입 설정, Student 객체
LinkedList<Student> members = new LinkedList<Student>(); 
// 타입 설정, int타입
LinkedList<Integer> num = new LinkedList<Integer>(); 
// new에서 타입 파라미터 생략 가능
LinkedList<Integer> num2 = new LinkedList<>(); 
// 생성 시 값 추가
LinkedList<Integer> list2 = new LinkedList<Integer>(Arrays.asList(1,2));

- LinkedList는 초기의 크기를 미리 설정할 수 없다.

- 타입 미설정 시 내부의 값을 사용할 때 캐스팅을 해야 하고 잘못된 타입으로 캐스팅한 경우 에러가 발생하기 때문에 권유하지 않는다.

 

LinkedList 값 추가

LinkedList<Integer> list = new LinkedList<Integer>();
list.addFirst(1); // 가장 앞에 데이터 추가
list.addLaast(2); // 가장 뒤에 데이터 추가
list.add(3);      // 인덱스 생략 시 가장 뒤에 데이터 추가
list.add(1, 10);  // 인덱스 1에 데이터 10 추가

LinkedList<Student> members = new LinkedList<Student>();
Student student = new Student("김영하", 20);
members.add(student);
members.add(new Student("이병률", 20));

 

LinkedList 값 삭제

LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1, 2, 3, 4));
list.removeFirst();
list.removeLast();
list.remove();		// 인덱스 생략 시 0번 째 인덱스 값 삭제
list.remove(1);		// 1번 째 인덱스 값 삭제
list.claer();		// 모든 값 삭제

 

LinkedList 크기 구하기

LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1, 2, 3));
System.out.println(list.size()); // 3

 

LinkedList 값 출력

LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1, 2, 3));
System.out.println(list.get(0)); // 0번 째 인덱스 값 출력

for(Integer i : list) {
	System.out.println(i);
}

Iterator<Integer> iter = list.iterator();
while(iter.hasNext()) {
	System.out.println(iter.next());
}

 

 

LinkedList 값 검색

LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1, 2, 3));
System.out.println(list.contains(1)); // list에 1이 있다면 true 반환
System.out.println(list.indexOf(1));  // 1이 있는 index, 없으면 -1 반환

 

 

참고

- [자료구조 알고리즘] Linked List 개념

- LinkedList - java 구현

- 자바 LinkedList 사용법 & 예제 총정리