> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/02-11-2022-71.md).

# 02/11/2022 71

[deque](https://docs.oracle.com/javase/10/docs/api/java/util/Deque.html): A linear collection that supports element insertion and removal at both ends.

As far as I know, LinkedLists take extra memory. Also, ArrayDeque is faster. Although this wont be seen under 10000 elements. So use ArrayDeque if u wanna add/remove items to both ends. Use LinkedLists if u r doing lots of add/remove in the middle.

```
 Summary of Deque methods
				
   First Element (Head)             |	Last Element (Tail)
       |Throws exception |	  Special value	|Throws exception|Special value
Insert |	addFirst(e)	 | offerFirst(e)|addLast(e)   |	  offerLast(e)
Remove |	removeFirst()   | pollFirst() 	|removeLast() |	  pollLast()
Examine|	getFirst()	 | peekFirst()	    |getLast()	 | peekLast()
```

```
String a = "/home/..////a/b/";
    String[] b = a.split("/");
    b ={"home", "..", "", "", "", "a", "b"}
```

```
class Solution {
    public String simplifyPath(String path) {
        //step 1: reform input. split based on slash
        //a = "/home/.././//a/b/"
        String[] clean = path.split("/");
        // b ={"home", "..", ".", "", "", "a", "b"}
        
        //step 2: process "..", which removes the previous string.
        //        process ".", which do nothing.
        //        process "", which do nothing.
        Deque<String> deque = new LinkedList<>();
        String[] skip = {"..",".", ""}; 
        Set<String> skip_set = new HashSet<>(Arrays.asList(skip));
        
        for(String s:clean){
            if(s.equals("..") && !deque.isEmpty()){
                deque.removeLast();
            }
            else if(!skip_set.contains(s)){
                deque.addLast(s);
            }
        }
        //StringBuilder is a mutable sequence of characters.
        //String is immutable.
		// So concatenate string will generate a new string each time, StrinbBuilder won't. Save space. ^-^
        StringBuilder output = new StringBuilder();
        for(String s:deque){
            output.append("/");
            output.append(s);
        }
        if(output.toString().equals("")) return "/";
        return output.toString();
    }     
}
```