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

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

Octave Linked List Implementation (Node Structure)

Octave

Goal -- WPM

Ready
Exercise Algorithm Area
1classdef Node

2% Represents a node in a singly linked list.

3properties

4data;      % The data stored in the node.

5next = []; % Reference to the next node in the list (initially empty).

6end

7

8methods

9function obj = Node(dataValue)

10% Constructor for the Node class.

11% Initializes the node with a given data value.

12if nargin > 0

13obj.data = dataValue;

14else

15obj.data = []; % Default to empty if no value provided.

16end

17end

18end

19end

20

21classdef LinkedList

22% Represents a singly linked list.

23properties

24head = []; % Reference to the first node in the list (initially empty).

25tail = []; % Reference to the last node in the list (initially empty).

26count = 0; % Number of nodes in the list.

27end

28

29methods

30function obj = LinkedList()

31% Constructor for the LinkedList class.

32% Initializes an empty linked list.

33obj.head = [];

34obj.tail = [];

35obj.count = 0;

36end

37

38function obj = addNode(obj, dataValue)

39% Adds a new node with the given data value to the end of the list.

40newNode = Node(dataValue);

41

42% Edge case: If the list is empty, the new node becomes both head and tail.

43if isempty(obj.head)

44obj.head = newNode;

45obj.tail = newNode;

46else

47% Otherwise, append the new node after the current tail.

48obj.tail.next = newNode;

49% Update the tail to be the new node.

50obj.tail = newNode;

51end

52% Increment the node count.

53obj.count = obj.count + 1;

54end

55

56function displayList(obj)

57% Displays the data of each node in the list, from head to tail.

58fprintf('List: ');

59currentNode = obj.head;

60while ~isempty(currentNode)

61fprintf('%s -> ', num2str(currentNode.data)); % Convert data to string for display

62currentNode = currentNode.next;

63end

64fprintf('NULL\n');

65end

66

67function dataArray = toArray(obj)

68% Converts the linked list to a standard Octave array.

69dataArray = zeros(1, obj.count);

70currentNode = obj.head;

71index = 1;

72while ~isempty(currentNode)

73dataArray(index) = currentNode.data;

74currentNode = currentNode.next;

75index = index + 1;

76end

77end

78end

79end
Algorithm description viewbox

Octave Linked List Implementation (Node Structure)

Algorithm description:

This Octave code defines a singly linked list data structure using classes. It includes a `Node` class to represent individual elements and a `LinkedList` class to manage the list's operations, such as adding nodes and displaying the list. Linked lists are fundamental for dynamic memory allocation and various data structure implementations.

Algorithm explanation:

The code defines two classes: `Node` and `LinkedList`. The `Node` class has properties for `data` and a `next` pointer, which refers to the subsequent node. The `LinkedList` class manages the `head`, `tail`, and `count` of the list. The `addNode` method creates a new `Node` and appends it to the end of the list. If the list is empty, the new node becomes both the `head` and `tail`. Otherwise, the `next` pointer of the current `tail` is updated to point to the new node, and the `tail` is updated. The `displayList` method traverses the list from the `head` to the `tail`, printing the `data` of each node. The `toArray` method converts the list into a standard Octave array. The time complexity for `addNode` is O(1) because it directly manipulates the `tail`. The `displayList` and `toArray` methods have a time complexity of O(n), where n is the number of nodes, as they iterate through the entire list. The space complexity is O(n) to store the nodes. An invariant for `addNode` is that after execution, `obj.tail.next` will point to the newly added node, and `obj.tail` will be that new node.

Pseudocode:

class Node:
  properties:
    data
    next = null
  methods:
    constructor(dataValue):
      this.data = dataValue

class LinkedList:
  properties:
    head = null
    tail = null
    count = 0
  methods:
    constructor():
      initialize head, tail to null, count to 0

    addNode(dataValue):
      newNode = new Node(dataValue)
      if head is null:
        head = newNode
        tail = newNode
      else:
        tail.next = newNode
        tail = newNode
      count = count + 1

    displayList():
      print 'List: '
      currentNode = head
      while currentNode is not null:
        print currentNode.data + ' -> '
        currentNode = currentNode.next
      print 'NULL'

    toArray():
      resultArray = empty array of size count
      currentNode = head
      index = 1
      while currentNode is not null:
        resultArray[index] = currentNode.data
        currentNode = currentNode.next
        index = index + 1
      return resultArray