ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:
Timer 00:00
WPM --
Score --
Acc --
Correct chars --

Implement a Doubly Linked List with Basic Operations

C++ (Unreal)

Goal -- WPM

Ready
Exercise Algorithm Area
1class Node

2{

3public:

4int data;

5Node* next;

6Node* prev;

7

8Node(int val) : data(val), next(nullptr), prev(nullptr) {}

9};

10

11class DoublyLinkedList

12{

13private:

14Node* head;

15Node* tail;

16int count;

17

18public:

19DoublyLinkedList()

20: head(nullptr), tail(nullptr), count(0) {}

21

22~DoublyLinkedList()

23{

24Node* current = head;

25while (current != nullptr)

26{

27Node* nextNode = current->next;

28delete current;

29current = nextNode;

30}

31head = nullptr;

32tail = nullptr;

33count = 0;

34}

35

36// Insert at the beginning

37void InsertAtBeginning(int val)

38{

39Node* newNode = new Node(val);

40if (head == nullptr)

41{

42head = newNode;

43tail = newNode;

44}

45else

46{

47newNode->next = head;

48head->prev = newNode;

49head = newNode;

50}

51count++;

52}

53

54// Insert at the end

55void InsertAtEnd(int val)

56{

57Node* newNode = new Node(val);

58if (tail == nullptr)

59{

60head = newNode;

61tail = newNode;

62}

63else

64{

65tail->next = newNode;

66newNode->prev = tail;

67tail = newNode;

68}

69count++;

70}

71

72// Delete by value

73bool DeleteByValue(int val)

74{

75if (head == nullptr)

76{

77return false; // List is empty

78}

79

80Node* current = head;

81while (current != nullptr)

82{

83if (current->data == val)

84{

85// Case 1: Deleting the head node

86if (current == head)

87{

88head = current->next;

89if (head != nullptr)

90{

91head->prev = nullptr;

92}

93else

94{

95// List becomes empty

96tail = nullptr;

97}

98}

99// Case 2: Deleting the tail node

100else if (current == tail)

101{

102tail = current->prev;

103tail->next = nullptr;

104}

105// Case 3: Deleting a middle node

106else

107{

108current->prev->next = current->next;

109current->next->prev = current->prev;

110}

111delete current;

112count--;

113return true;

114}

115current = current->next;

116}

117return false; // Value not found

118}

119

120// Search for a value

121bool Search(int val) const

122{

123Node* current = head;

124while (current != nullptr)

125{

126if (current->data == val)

127{

128return true;

129}

130current = current->next;

131}

132return false;

133}

134

135// Print the list (forward)

136void PrintForward() const

137{

138Node* current = head;

139UE_LOG(LogTemp, Warning, TEXT("List (Forward): "));

140while (current != nullptr)

141{

142UE_LOG(LogTemp, Warning, TEXT("%d -> "), current->data);

143current = current->next;

144}

145UE_LOG(LogTemp, Warning, TEXT("nullptr"));

146}

147

148// Print the list (backward)

149void PrintBackward() const

150{

151Node* current = tail;

152UE_LOG(LogTemp, Warning, TEXT("List (Backward): "));

153while (current != nullptr)

154{

155UE_LOG(LogTemp, Warning, TEXT("%d -> "), current->data);

156current = current->prev;

157}

158UE_LOG(LogTemp, Warning, TEXT("nullptr"));

159}

160

161// Get the number of elements

162int GetCount() const

163{

164return count;

165}

166

167// Check if the list is empty

168bool IsEmpty() const

169{

170return count == 0;

171}

172

173// Get head value (for testing)

174int GetHeadValue() const

175{

176if (head == nullptr)

177{

178// In a real Unreal project, you might throw an exception or return a default/error value.

179// For this example, returning a sentinel value.

180return -1; // Indicate error or empty list

181}

182return head->data;

183}

184

185// Get tail value (for testing)

186int GetTailValue() const

187{

188if (tail == nullptr)

189{

190// In a real Unreal project, you might throw an exception or return a default/error value.

191// For this example, returning a sentinel value.

192return -1; // Indicate error or empty list

193}

194return tail->data;

195}

196};
Algorithm description viewbox

Implement a Doubly Linked List with Basic Operations

Algorithm description:

This C++ code defines a Doubly Linked List data structure with essential operations. A doubly linked list allows traversal in both forward and backward directions. It's commonly used in scenarios requiring efficient insertion/deletion at arbitrary positions, such as implementing undo/redo functionality, managing browser history, or building caches.

Algorithm explanation:

The Doubly Linked List implementation involves a `Node` struct with `data`, `next`, and `prev` pointers, and a `DoublyLinkedList` class managing `head`, `tail`, and `count`. Insertion at the beginning and end involves creating a new node and carefully updating pointers of the new node and the existing head/tail. Deletion by value requires traversing the list, finding the node, and then reconnecting the `prev` and `next` pointers of its neighbors, with special handling for deleting the head or tail. Searching is a simple linear traversal. The destructor iterates through the list, deleting each node to prevent memory leaks. Time complexity for insertion, deletion, and search is O(n) in the worst case (traversing the list), but O(1) for insertion at head/tail if the pointers are maintained. Space complexity is O(n) to store n elements. Edge cases like an empty list, deleting the only node, or deleting the head/tail are handled explicitly to ensure pointer integrity.

Pseudocode:

class Node:
  data
  next_pointer
  prev_pointer

class DoublyLinkedList:
  head_pointer
  tail_pointer
  size_count

function InsertAtBeginning(value):
  create newNode with value
  if list is empty:
    set head = newNode
    set tail = newNode
  else:
    set newNode.next = head
    set head.prev = newNode
    set head = newNode
  increment size_count

function InsertAtEnd(value):
  create newNode with value
  if list is empty:
    set head = newNode
    set tail = newNode
  else:
    set tail.next = newNode
    set newNode.prev = tail
    set tail = newNode
  increment size_count

function DeleteByValue(value):
  if list is empty:
    return false
  iterate through list from head:
    if current_node.data == value:
      if current_node is head:
        update head to current_node.next
        if new head is not null, set new_head.prev = null
        else set tail = null
      else if current_node is tail:
        update tail to current_node.prev
        set new_tail.next = null
      else:
        set current_node.prev.next = current_node.next
        set current_node.next.prev = current_node.prev
      delete current_node
      decrement size_count
      return true
  return false (value not found)

function Search(value):
  iterate through list from head:
    if current_node.data == value:
      return true
  return false