8-LinkedList

LinkedList和array的优缺点

	Linked List	Array
优点	1，they can adapt their ordering by changing the items they point to – no memory is wasted 3，extra links can easily be added	1，New elements can be stored anywhere and a reference is created for the new element using pointers. 2，Random accessing is possible. 3，Memory is allocated during the run-time (Dynamic memory allocation). 4，Array elements can be accessed randomly using the array index. 5，Insertion and Deletion operations are fast and easy.
缺点	1，With a linked list, if we need to find the special link, we have to start at the beginning of the chain, and work the way along in order to find an item 2，Binary search not possible – big disadvantage of linked lists	1. waste space 2. not easy to extend an array. Size of the array must be specified at the time of array declaration/initialization. 3. to insert a new element is not easy

Linked List	头节点=空数据+第一个link的reference	
Double-Ended Linked Lists	头节点=first reference+last reference	
Singly Linked List	无上述的头节点，直接第一个开始【data+reference】	
Sorted Lists
Doubly Linked Lists	头节点=first reference+last reference	

一、Linked List 1， A linked list is an abstract data structure consisting of a sequence of links

• Link objects are created for each link in the list • All contain references to the next link in the list

2，结构 这里的first相当于head，头结点,不存储数据，只是一个指向头 this is only a reference to the next Link，does not represent the actual object itself

• Linked list only contains a reference to the first link • This is originally set to null

2，操作 • The head is the first link • The tail is the last link

Inserting at the Head
• 1. Create a new link • 2. Have new link point to old first link • 3. Update Linked List to point to new link 	

Deleting at the Head
• Update head to point to next node in the list • Garbage collector will now reclaim the former first node 	

Traversing a linked list
必须从头开始遍历， 而且二分法不能用【大大滴缺点】	

find or delete one particular node
• Take in the value to be found or deleted • Start at the beginning of the list • Keep moving down the links until we find the correct one • All the while keep tracking the current link and the previous link (so we can join them up when required) • Now update the references to bypass the link to be deleted 	

二、Double-Ended Linked Lists 双头链表 1，• It as a reference to the last link as well as the first

2，操作

Inserting at the Tail
• Create a new link • Have new link point to null • Have old last link point to new node • Update tail of Linked List object to point to new node	

Removing at the Tail
• Removing at the tail of a singly-linked double ended list is not efficient! • There is no constant time way to update the tail to point to the previous node • We need to use double links (that point to both next and previous link)	

三、Linked-List Efficiency 用堆栈来实现均可

四、Singly Linked List 1，Stack with a Singly Linked List 此时无头结点 • The top element is stored at the first node of the list • The space used is 𝑶(𝒏) and each operation of the Stack ADT takes 𝑶(𝟏) time

2，Queue with a Singly Linked List • The front element is stored at the first node • The rear element is stored at the last node

五、Sorted Lists priority queue – this required the items to be sorted 1，Only way to find the correct location is to search through the list – can’t use binary search • When you find the correct location (i.e. when you find a value bigger than the one you want to insert) update the pointers of the relevant links

2，操作

Insertion
The new element must be set to point to the next element in the linked list The previous element must be updated to point to the new element 	

3、Efficiency of Sorted Linked Lists

4，Using linked lists for array sorting

六、Doubly Linked Lists 双链表 单链表不能backwards 1，A linked list where you can traverse it forwards or backwards is a doubly linked list (references going both ways)

现在是data+（next reference和prev reference） 操作的时候记得更新两个索引 list中， first头结点的next是第一个link 第一个link的pre是空，	

2，操作

Insertion at begining
– Change prev of first link – Change next of new link – Change first of Linked List 	

Insertion in order
 	

Deletion
– Change next of left link – Change prev of right link 	

七、Iterators[!!重点，看不懂]

1，• Iterators always point to some link in the list • They are associated with the list but are not part of it

2，Objects containing references to items in data structures, used to traverse these structures, are commonly called iterators

• If our linked list isn’t doubly-linked then the iterator should store both current and previous so that it can delete links • It is also handy for the iterator to store a reference to the linked list class so it can access the first element of the list

3，操作

Removing a Link using the Iterator【注意】


Adding a Link using the Iterator【注意】

The atEnd() Method


Stacks using Linked Lists


Linked List代码