DeleteTail function in Linked List

How do I implement the "deletetail" function and the "get length" function?

Thanks.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
using namespace std;

class Node
{
public:
	int value;
	Node * next;
	Node();
	Node(int);
};
Node::Node():value(0),next(NULL){}
Node::Node(int v):value(v),next(NULL){}

void Print(Node* h)
{
	while(h)
	{
		cout<<" -> "<<h->value;
		h=h->next;
	}
	cout<<endl;
}
void Create(Node*& head, int n)
{
	head = new Node(1);
	Node * tmp=head;
	for(int i=2; i<=n; i++)
	{
		tmp->next = new Node(i);
		tmp = tmp->next;
	}
}

void AddHead(Node*& head, int n)
{
	Node * tmp = new Node(n);
	tmp->next = head;
	head=tmp;
}

void AddTail(Node*& head, int n)
{
	Node* tmp = new Node(n);
	if(!head)
	{
		head=tmp;
		return;
	}
	Node * t=head;
	while(t->next) t=t->next;
	t->next=tmp;
}


void DeleteHead(Node*& head)
{
	if(!head) return;
	Node* tmp = head;
	head = head->next;
	delete tmp;
}

int main()
{
	Node * h = NULL; //this is the head of the list
	cout<<"first manually create 3 nodes and link them together\n";
	Node* one = new Node(1);
	Node* two = new Node(2);
	Node* three = new Node(3);
	h=one;
	one->next=two;
	two->next=three;
	Print(h);
	cout<<"now call Create() function to create 8 nodes\n";
	Create(h, 8);
	Print(h);
	cout<<"adding a node with value 44 at the head of existing list\n";
	AddHead(h, 44);
	Print(h);
	cout<<"adding a node with value 55 at the tail of existing list\n";
	AddTail(h, 55);
	Print(h);
	cout<<"deleting head\n";
	DeleteHead(h);
	Print(h);
	return 0;
}
Last edited on
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>

struct Node
{
    int value;
	Node* next;
	/*explicit*/ Node( int v = 0, Node* nxt = nullptr ) : value(v), next(nxt) {}
};

std::size_t length( const Node* head )
{
    std::size_t n = 0 ;
    for( const Node* current = head ; current != nullptr ; current = current->next ) ++n ;
    return n ;
}

Node* delete_tail( Node*& head )
{
    if( head == nullptr ) return nullptr ;

    else if( head->next == nullptr ) { delete head ; head = nullptr ; } // delete the only element

    else // at least two elements
    {
        // get to the node just before the last node
        Node* prev = head ;
        for( Node* current = head->next ; current->next != nullptr ; current = current->next ) prev = current ;

        delete prev->next ; // delete the last element
        prev->next = nullptr ;
    }

    return head ;
}

int main()
{
    Node* list = new Node( 23, new Node( 35, new Node( 12, new Node( 48, new Node( 28, new Node( 90, new Node(73) )))))) ;

    while( list != nullptr )
    {
        for( Node* current = list ; current != nullptr ; current = current->next )
            std::cout << current->value << " --> " ;
        std::cout << "nullptr    (length:" << length(list) << ")\n" ;

        delete_tail(list) ;
    }
}

http://coliru.stacked-crooked.com/a/b4c2536c643ee272
Topic archived. No new replies allowed.