C++

Forum

 
Linked list

bowlbase (25)
So I'm having a little trouble with trying to make a swap function that can deal with all of the possible circumstances in a doubly linked list (=head&&=tail, =head&& !=tail, etc). I think I have it complete but I wanted to ask if anyone saw problems with it. It compiles fine but I don't have a way to check it at the moment. 

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
  void List<T>::reverse( ListNode * & startPoint, ListNode * & endPoint )
{

	ListNode * s = startPoint;
	ListNode * e = endPoint;

if(startPoint == endPoint){return;}
if(startPoint == NULL || endPoint == NULL){return;}

	ListNode * r;
	ListNode * x;
	r = s->next;
	x = e->prev;

if(startPoint == endPoint){return;}
if(startPoint == NULL || endPoint == NULL){return;}



	while(s!=e)
	{
	swap(s,e);
	s=r;
	e=x;
	r = s->next;
	x = e->prev;
	}
        //find the head
	while(head->prev != NULL)
	{
        head = head->prev;
	}
        //find the tail
    	while(tail->next != NULL)
    	{
        tail = tail->next;
    	}
}
//Swap class does the grunt work for reverse. It first checks to see if the nodes 
//are usable. Then it checks the conditions of the nodes (head or tail) and swaps 
//them according to their condition. This lets reverse only worry about whether
//snode == enode
template <class T>
void List<T>::swap( ListNode * & snode, ListNode * & enode )
{
	
	ListNode * s = snode;
	ListNode * e = enode;
	ListNode * r;
	ListNode * x;
	ListNode * y;
	ListNode * t;

	//Are they the same?
	if(s == e) return;
	//if given null nodes
	if (s == NULL || e == NULL) return;

	//if they are head and tail nodes but not next to each other
	if(s==head && e==tail && s->next != e->prev)
	{
	r = s->next;
	x = e->prev;
	s->next = NULL;
	s->prev = x;
	e->prev = NULL;
	e->next = r;

	}

	else
	//if nodes are next to each other
	if(s->next == e->prev)
	{
		if(s!=head && e!=tail)
		{
		t = s->prev;
		y = e->next;
		s->next = y;
		s->prev = e;
		e->prev = t;
		e->next = s;
		}
		else
		if(s==head && e!=tail)
		{
		y = e->next;
		s->next = y;
		s->prev = e;
		e->prev = NULL;
		e->next = s;
		}		
		else
		if(s!=head && e==tail)
		{
		t = s->prev;
		s->next = NULL;
		s->prev = e;
		e->prev = t;
		e->next = s;
		}	
		else
		if(s==head && e==tail)
		{
		s->next = NULL;
		e->prev= NULL;
		e->next=s;
		s->prev=e;
		}	
	}

	else
	//if not heads or tails and not next to eachother. middle of list.
	if(s !=head && e != tail && s->next != e->prev)
	{
	t = s->prev;
	r = s->next;
	x = e->prev;
	y = e->next;
	t->next = e;
	r->prev = e;
	e->prev = t;
	e->next = r;
	x->next = s;
	y->prev = s;
	s->next = y;
	s->prev = x;
	}
	
	else
	//if head but not tails and not next to each other
	if(s==head && e!=tail && s->next != e->prev)
	{
	r = s->next;
	x = e->prev;
	y = e->next;
	s->prev = x;
	s->next = y;
	e->prev = NULL;
	e->next = r;

	}
	else
	//if not head but is tail and not next to each other
	if(s!=head && e==tail && s->next != e->prev)
	{
	r = s->next;
	x = e->prev;
	t = s->prev;
	s->prev = x;
	s->next = NULL;
	e->prev = t;
	e->next = r;

	}




}


I understand it isn't built for speed or efficiency. I just want to make sure I have the general idea. Perhaps I can go back and try to use few pointers when I have time.

Thanks for the help.
Smac89 (1727)
Instead of swapping the links, why not leave them the way they are and just swap the data they contain? This is still equivalent to reversing the list

1
2
3
4
5
6
7
8
9
10
11
12
13
 
void List<T>::reverse( ListNode *startPoint, ListNode *endPoint ) {
    if (startPoint == nullptr || endPoint == nullptr) return;

    for ( T temp; startPoint != endPoint; ) {
        temp = startPoint->data;
        startPoint->data = endPoint->data;
        endPoint->data = temp;
    
        startPoint = startPoint->next;
        if (startPoint == endPoint) break; // handle even length cases
        endPoint = endPoint->prev;
    }
}

bowlbase (25)
I don't even know what to say. It never occurred to me to even think about the data. I was just thinking of the nodes. All this time I've wasted trying to think of ways to do this..

Thanks.
Topic archived. No new replies allowed.