1. When we use a singly linked list to implement a stack, which side of the list
ID: 3593761 • Letter: 1
Question
1. When we use a singly linked list to implement a stack, which side of the list should be used as the top of the stack? Why?
2. When we use a singly linked list to implement a queue, which side of the list should be used as the front of the queue? Why? Type your answer below
3. Given an empty unsorted singly link list object for integers, and call the following 8 functions in sequence. Draw the resulted linked list with all links and members in the linked list object on your answer sheet
AddToHead(5)
AddToTail(87)
AddToHead (6)
AddToTail(43)
AddToHead (2)
DeleteNode(4)
DeleteNode(87)
AddToHead (15)
4. Given an empty array based unsorted list object for integers, and run the following 8 functions in sequence. List the resulted list starting from the element at index 0 separated by space
InsertItem(5)
InsertItem(87)
InsertItem(6)
InsertItem(43)
InsertItem(2)
DeleteItem(4)
DeleteItem(87)
InsertItem(15)
Paragraph answers please and use proper grammar
Explanation / Answer
1. When we use a singly linked list to implement a stack, which side of the list should be used as the top of the stack? Why?
Head of the list should be used as top of the stack so that every push and pop (or top/peek) operation can be done in constant time.
If you use tail pointer then every time you want to push or pop an element you need to traverse the whole list.
2. When we use a singly linked list to implement a queue, which side of the list should be used as the front of the queue? Why? Type your answer below
Its better to use head as front of queue (and tail as Rear), so that every dequeue operation is O91) by just removing head (enqueue can also be made O(1) by just keeping tail pointer in memory)
3. Given an empty unsorted singly link list object for integers, and call the following 8 functions in sequence. Draw the resulted linked list with all links and members in the linked list object on your answer sheet
AddToHead(5)
AddToTail(87)
AddToHead (6)
AddToTail(43)
AddToHead (2)
DeleteNode(4)
DeleteNode(87)
AddToHead (15)
Ans 3.
Here is image of list after each operation given in order
5-> null
5->87->null
6->5->87->null
6->5->87->43->null
2->6->5->87->43->null
2->6->5->87->43->null
2->6->5->87->43->null
15->2->6->5->43->null
4. Given an empty array based unsorted list object for integers, and run the following 8 functions in sequence. List the resulted list starting from the element at index 0 separated by space
InsertItem(5)
InsertItem(87)
InsertItem(6)
InsertItem(43)
InsertItem(2)
DeleteItem(4)
DeleteItem(87)
InsertItem(15)
Ans4:
5
5 87
5 87 6
5 87 6 43
5 87 6 43 2
5 87 6 43 2
5 6 43 2
5 6 43 2 15
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.