StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
7733122
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
0
CommunityOwnedDate
CreationDate
2011-10-11T22:08:43.237
FavoriteCount
0
LastActivityDate
2011-10-11T22:08:43.237
LastEditDate
LastEditorUserId
0
OwnerUserId
580637
ParentId
7732820
PostTypeId
2
Score
0
ViewCount
0
LastEditorDisplayName
text
Body
Perhaps you need to think a little deeper on the implementation of linked lists. You indicate that lazy deletion would NOT help in any way because the time to search is all the time that is necessary to perform the delete. Think about what it takes to actually REMOVE an item from a linked list. note: this assumes a SINGLY linked list (not a double linked list) 1) Find the item to delete (because this is a SINGLE linked list, you always have to search, because you need the PREV item) 2) Keep pointers to the PREV and NEXT elements 3) Fix the "PREV" element to point to the NEXT element - thus, isolating the CURRENT element 3.5) in a double linked list, you also have to take care of the NEXT element pointing back to the PREV element. 4) Release the memory associated with CURRENT element Now, what is the process for a lazy delete? --- much shorter 1) Find the item to delete (you may not even have to perform a search, as you already have a pointer to the object you want deleted?) 2) mark the item for deletion. *) Wait for "Garbage collection" thread to run and actually perform the remaining steps WHEN the system is "IDLE" A binary tree implemented as a linked list where each element has a left and a right - however, you still perform the same steps in the search. Binary tree searching is just more efficient with O(Log(n)) I believe. However, deleting from these becomes more complex because you have more pointers to deal with (both a "LEFT" and a "RIGHT") - so will take more instructions to fix, especially when you are deleting a tree node that has pointers to nodes for both the left and right -- one of them will need to be promoted to the new root - however, what if they also both already have their left and right pointers assigned? where does the original "left/right" node go? - You have to re-balance the tree at this point. Thus, there is significant savings by mark for delete from a user perspective and having an "idle" garbage collection taking care of the memory details (so the user doesn't have to wait for that).
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POHow is lazy deletion advantageous/disadvantageous to a binary tree or linked list?
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. This table or related slice is empty.
UserOwnerUserId
1. USSilverKnight
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. This table or related slice is empty.
CommentsPostId
1. This table or related slice is empty.

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.