Single Linked List Concepts

What is the basic structure of a node in a single linked list?

• A node in a singly linked list consists of multiple data fields without any pointers.

• A node in a singly linked list contains only a data field.

• A node in a singly linked list has a data field and a pointer to the next node.

• A node in a singly linked list has two pointers, one for the next node and one for the previous node.

Write pseudocode to insert a node at the beginning of a single linked list.

• function addNodeToEnd(head, newData) { newNode = new Node(newData); if (head == null) { head = newNode; } else { current = head; while (current.next != null) { current = current.next; } current.next = newNode; } return head; }

• function insertAtPosition(head, newData, position) { newNode = new Node(newData); if (position == 0) { newNode.next = head; head = newNode; return head; } current = head; for (i = 0; i < position - 1 && current != null; i++) { current = current.next; } newNode.next = current.next; current.next = newNode; return head; }

• function insertAtBeginning(head, newData) { newNode = new Node(newData); newNode.next = head; head = newNode; return head; }

• function deleteFromBeginning(head) { if (head == null) return null; head = head.next; return head; }

Describe the pseudocode for inserting a node at the end of a single linked list.

• 1. Create a new node. 2. If head is null, set head to new node. 3. Else, set current to head. 4. While current.next is not null, set current to current.next. 5. Set current.next to new node.

• 1. Create a new node. 2. If head is not null, set head to new node. 3. Set current to head. 4. While current.next is null, set current to current.next. 5. Set current.next to new node.

• 1. Create a new node. 2. Set head to null. 3. Set current to tail. 4. While current is not null, set current to current.previous. 5. Set current.previous to new node.

• 1. Create a new node. 2. Set head to new node. 3. Set current to head. 4. While current.next is null, set current to current.next. 5. Set current.next to null.

What is the pseudocode for deleting a node from a single linked list?

• Set head.next = head to delete the node.

• 1. If head is null, return. 2. If head is the node to delete, set head = head.next. 3. Initialize current = head. 4. While current.next is not null: 5. If current.next is the node to delete: 6. Set current.next = current.next.next. 7. Return.

• If head is null, set head to the node to delete.

• Traverse the list and print each node's value.

Explain how to traverse a single linked list and write the pseudocode for it.

• Print currentNode.next.value

• Pseudocode: 1. Set currentNode = head 2. While currentNode is not null: a. Print currentNode.value b. Set currentNode = currentNode.next

• While currentNode is null:

• Set currentNode = tail

What is the time complexity of traversing a single linked list?

• O(1)

• O(n^2)

• O(n)

• O(log n)

Write pseudocode to search for a value in a single linked list.

• function locateValue(head, target) { current = head; if (current.value == target) { return current; } return null; }

• function searchList(head, target) { for (let node of head) { if (node.value == target) { return node; } } return null; }

• function findInList(head, value) { while (head != null) { if (head.value != value) { head = head.next; } } return head; }

• function searchLinkedList(head, target) { current = head; while (current != null) { if (current.value == target) { return current; } current = current.next; } return null; }

What is the difference between linear search and binary search in the context of linked lists?

• Linear search requires more memory than binary search.

• Binary search can be applied to unsorted linked lists.

• Linear search can be used on linked lists, while binary search cannot due to the lack of random access.

• Binary search is faster than linear search on linked lists.

How would you implement a function to count the number of nodes in a single linked list?

• Count nodes by recursively traversing the list without a base case.

• Use a stack to store nodes and return the stack size.

• Define a function that iterates through the linked list, counting each node until the end is reached.

• Count nodes by summing the values of each node.

What are the advantages of using a single linked list over an array?

• Advantages of using a singly linked list over an array include dynamic size, efficient insertions and deletions, and non-contiguous memory allocation.

• Easier to implement than arrays

• Slower access time for elements

• Fixed size allocation