연결리스트 개념

Git : https://github.com/mongsilJeong/algorithm/blob/master/src/algorithm/codingInterview/datastructure/linkedList/LinkedList.java

 

LinkedList란?

 

연결리스트LinkedList는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조이다. 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당한다. 중간에 데이터를 추가나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없기에 ArryaList에 비해서 데이터의 추가나 삭제가 용이하나, 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차탐색이 필요하여 탐색속도가 떨어진다는 단점이 있다. 그러므로 탐색 또는 정렬을 자주 하는 경우엔 배열을 사용하고 데이터의 추가/삭제가 많은 경우 연결 리스트를 사용하는 것이 좋다.

 

배열은 (1) 크기를 정해야 한다. (2) 특정 인덱스를 상수 시간에 접근할 수 있다. (3) 아이템 추가/삭제 연산을 하려면 빈자리를 만들기 위해 다른 데이터들을 SWAP 해야한다.

 

배열과 달리 연결리스트는 (1) 특정 인덱스를 상수 시간에 접근할 수 없다. (2) 아이템을 추가하거나 삭제하는 연산을 상수 시간에 할 수 있다.

 

1. 단반향 연결리스트

class Node {
    int data;
    Node next = null;
}

단순히 다음 노드를 가르킨다.

 

 

2. 양방향 연결리스트 (doubly linked list)

class Node {
    int data;
    Node next;
    Node prev;
}

다음 노드의 주소도 가지고 있으며 그 전 노드의 주소도 가지고 있다.

 

---

자바로 단방향 링크드리스트를 구현

public class LinkedList {
	
	Node header; // 첫번째 노드를 가리키는 헤더
	
	// 노드 생성자
	static class Node {
		int data;
		Node next = null;
	}
	
	LinkedList() {
		header = new Node();
	}
	
	void append(int d) {
		Node end = new Node();
		end.data = d;
		
		Node n = header;
		while(n.next != null) {
			n = n.next;
		}		
		n.next = end;		
	}
	
	void delete(int d) {
		Node n = header;
		while(n.next != null) { // header는 값을 가지고 있지않기 때문에, n.next는 첫번째 노드를 가르키게 된다.
			if(n.next.data == d) {
				n.next = n.next.next;
			} else {
				n = n.next;
			}
		}
	}
	
	void retrieve() {
		Node n = header.next;
		while(n.next != null) {
			System.out.print(n.data + " -> ");
			n = n.next;
		}
		System.out.print(n.data);
		System.out.println();
	}

	public static void main(String args[]) {
		
		LinkedList ll = new LinkedList();
		
		ll.append(1);
		ll.append(2);
		ll.append(3);
		ll.append(4);
		ll.retrieve();
		ll.delete(1);
		ll.retrieve();
		
	}

 

Java로 양방향 링크드 리스트 구현

public class DoubleLinkedList {
	
	Node header;
	Node tail;
	
	class Node {
		int data;
		Node next = null;
		Node prev = null;
		
		public Node() {
			
		}
		public Node(int data) {
			this.data = data;
		}
	}
	
	public DoubleLinkedList() {
		this.header = new Node();
		this.tail = new Node();
	}
	
	/**
	 * 링크드리스트 맨 끝에 추가
	 * @param data
	 */
	void insert(int data) {
		Node n = header; 
		
		while(n.next != null) {
			n = n.next;
		}
		
		Node node = new Node(data);		
		n.next = node;
		node.prev = n;	
		tail = node; // tail 갱신		
	}
	
	/**
	 * 특정 노드 앞에 데이터 추가
	 * @param target
	 * @param data
	 */
	void insertBefore(int target, int data) {
		
		Node n = header.next;
		
		while(n != null) {
			if(n.data == target) {
				break;
			} else {
				n = n.next;
			}
		}		
		if(n == null) { // 데이터 못찾음
			System.out.println("Cannot find data");
			return;
		}
		Node node = new Node(data);
		
		Node beforeNew = n.prev;
		beforeNew.next = node;
		node.prev = beforeNew;
		
		node.next = n;
		n.prev = node;
		
	}
	
	/**
	 * Head 부터 Search
	 * @param data
	 * @return
	 */
	Node searchFromHead(int data) {
		Node n = header.next;
		while(n != null) {
			if(n.data == data) {
				return n;
			} else {
				n = n.next;
			}
		}
		return null;
	}
	
	/**
	 * Tail 부터 Search
	 * @param data
	 * @return
	 */
	Node searchFromTail(int data) {
		Node n = tail;
		while(n != null) {
			if(n.data == data) {
				return n;
			} else {
				n = n.prev;
			}
		}
		return null;
	}
	
	void retrieve() {
		Node n = header.next;
		while(n != null) {
			System.out.println(n.data);
			n = n.next;
		}
	}
	
	public static void main(String args[]) {
		DoubleLinkedList dlist = new DoubleLinkedList();
		for(int i=0; i<10; i++) {
			dlist.insert(i);
		}
		
		Node n_9 = dlist.searchFromTail(9);
		System.out.print(n_9.data);
		
		dlist.insertBefore(10, 0);
		dlist.retrieve();
	}

}

---

Java LinkedList

TheLinkedListclass is almost identical to theArrayList

// Import the LinkedList class
import java.util.LinkedList;

public class MyClass {
  public static void main(String[] args) {
    LinkedList<String> cars = new LinkedList<String>();
    cars.add("Volvo");
    cars.add("BMW");
    cars.add("Ford");
    cars.add("Mazda");
    System.out.println(cars);
  }
}

However, while theArrayListclass and theLinkedListclass can be used in the same way, they are built very differently.

How the ArrayList works

TheArrayListclass has a regular array inside it. When an element is added, it is placed into the array. If the array is not big enough, a new, larger array is created to replace the old one and the old one is removed.

How the LinkedList works

TheLinkedListstores its items in "containers." The list has a link to the first container and each container has a link to the next container in the list. To add an element to the list, the element is placed into a new container and that container is linked to one of the other containers in the list.

When To Use

It is best to use anArrayListwhen:

• You want to access random items frequently
• You only need to add or remove elements at the end of the list

It is best to use aLinkedListwhen:

• You only use the list by looping through it instead of accessing random items
• You frequently need to add and remove items from the beginning or middle of the
list

LinkedList Methods

Method	Description
addFirst()	Adds an item to the beginning of the list.
addLast()	Add an item to the end of the list
removeFirst()	Remove an item from the beginning of the list.
removeLast()	Remove an item from the end of the list
getFirst()	Get the item at the beginning of the list
getLast()	Get the item at the end of the list